Background

一共有N个城市，每座城市可能会有双向公路连接起来，总共有M条公路。Viete生活在S市。他想知道从S市到其他城市怎样走才最省时间。

Description

这个问题显然太简单了，所以Viete还想知道一共有多少不同的最省时的方案数，当然，如果从S这里到不了某一个城市，就输出0。

Format

Input

第一行3个正整数\(N,M,S\)，为城市数、公路数与Viete所在的城市。

接下来\(M\)行，每行2个正整数\(x,y\)，表示有一条城市\(x\)连向城市\(y\)的边，请注意可能有自环与重边。

Output

共\(N\)行，每行一个非负整数，第\(i\)行输出从城市\(S\)到城市\(i\)有多少条不同的最省时的方案数。

Sample 1

Input

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

Output

1
1
1
2
4

Limitation

\(1 \le S \le N \le 1000000,1 \le M \le 2000000\)

由于答案有可能会很大，你只需要输出\(ans \bmod 2580000\)后的结果即可。