問題文

NN 頂点 NN 辺の有向グラフが与えられます。 このグラフには自己ループや多重辺は存在しません。 また、どの頂点にもそこから出る辺がちょうど 11 本だけ存在します。

ii 番目の辺は頂点 AiA_i を出て、頂点 BiB_i に入ります。

高橋くんははじめ、このグラフの頂点 11 に立っています。 すぬけくんが叫ぶ度に、高橋くんはその時立っている頂点から出る唯一の辺を通って次の頂点に移動し、そこに立ちます。

今、すぬけくんが KK 回叫びました。

i=1,2,,Ni = 1, 2, \ldots, N について、高橋くんが頂点 ii に立った回数を求めてください。

制約

  • 2N2×1052 \le N \le 2\times 10^5
  • 1Ai,BiN1 \le A_i, B_i \le N
  • AiBiA_i \ne B_i
  • 1K10181 \le K \le 10^{18}
  • 自己ループや多重辺は存在しない
  • どの頂点からも辺をたどることで行けるような頂点が存在する
  • 入力はすべて整数である

入力

N KA1 B1A2 B2AN BNN\ K\\ A_1\ B_1\\ A_2\ B_2\\ \vdots\\ A_N\ B_N

出力

NN 行出力せよ。

i=1,2,,Ni = 1, 2, \ldots, N について、 ii 行目には、高橋くんが頂点 ii に立った回数を出力せよ。

入出力例

入力例1
3 5
1 2
2 3
3 1
出力例1
2
2
2

高橋くんは頂点を 1231231 \to 2 \to 3 \to 1 \to 2 \to 3 と移動します。

入力例2
5 5
1 2
2 3
3 4
4 2
5 3
出力例2
1
2
2
1
0

高橋くんは頂点を 1234231 \to 2 \to 3 \to 4 \to 2 \to 3 と移動します。

入力例3
7 2000000
1 6
2 3
3 5
4 2
5 7
6 5
7 3
出力例3
1
0
666666
0
666667
1
666666

Submit


Go (1.21)