問題文
N 頂点 N 辺の有向グラフが与えられます。
このグラフには自己ループや多重辺は存在しません。
また、どの頂点にもそこから出る辺がちょうど 1 本だけ存在します。
i 番目の辺は頂点 Ai を出て、頂点 Bi に入ります。
高橋くんははじめ、このグラフの頂点 1 に立っています。
すぬけくんが叫ぶ度に、高橋くんはその時立っている頂点から出る唯一の辺を通って次の頂点に移動し、そこに立ちます。
今、すぬけくんが K 回叫びました。
i=1,2,…,N について、高橋くんが頂点 i に立った回数を求めてください。
制約
- 2≤N≤2×105
- 1≤Ai,Bi≤N
- Ai=Bi
- 1≤K≤1018
- 自己ループや多重辺は存在しない
- どの頂点からも辺をたどることで行けるような頂点が存在する
- 入力はすべて整数である
入力
出力
N 行出力せよ。
i=1,2,…,N について、 i 行目には、高橋くんが頂点 i に立った回数を出力せよ。
入出力例
高橋くんは頂点を 1→2→3→1→2→3 と移動します。
入力例2
5 5
1 2
2 3
3 4
4 2
5 3
高橋くんは頂点を 1→2→3→4→2→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