問題文

$N$ 頂点の有向グラフがあります。$N$ 個の頂点はそれぞれ頂点 $1$ 、頂点 $2$ 、$\\ldots$、頂点 $N$ と呼ばれます。 時刻 $0$ には、このグラフには辺がありません。

$t = 1, 2, \\ldots, T$ について、時刻 $t$ に頂点 $u_t$ から頂点 $v_t$ への有向辺が追加されます。 （追加される辺が自己ループである場合、すなわち $u_t = v_t$ の場合もあります。）

頂点 $1$ から始め「現在いる頂点からちょうど $1$ 本の有向辺をたどって到達できる頂点を $1$ つ選び、選んだ頂点に移動する」ことをちょうど $L$ 回繰り返して到達できる頂点を「良い頂点」と呼びます。

$i = 1, 2, \\ldots, N$ について、頂点 $i$ が良い頂点となる最小の時刻を出力してください。ただし、頂点 $i$ が良い頂点となる時刻が存在しない場合は、代わりに $\-1$ を出力してください。

制約

• $2 \\leq N \\leq 100$
• $1 \\leq T \\leq N^2$
• $1 \\leq L \\leq 10^9$
• $1 \\leq u_t, v_t \\leq N$
• $i \\neq j \\Rightarrow (u_i, v_i) \\neq (u_j, v_j)$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $T$ $L$ $u_1$ $v_1$ $u_2$ $v_2$ $\\vdots$ $u_T$ $v_T$

出力

下記の形式の通り、$i = 1, 2, \\ldots, N$ について、頂点 $i$ が良い頂点となる最小の時刻 $X_i$ を出力せよ。ただし、頂点 $i$ が良い頂点となる時刻が存在しない場合は、$X_i = -1$ とせよ。

$X_1$ $X_2$ $\\ldots$ $X_N$

入力例 1

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

出力例 1

-1 4 5 3

時刻 $0$ ではグラフは辺を持ちません。その後、以下の通りに辺の追加が行われます。

• 時刻 $1$ に、頂点 $2$ から頂点 $3$ への有向辺が追加されます。
• 時刻 $2$ に、頂点 $3$ から頂点 $4$ への有向辺が追加されます。
• 時刻 $3$ に、頂点 $1$ から頂点 $2$ への有向辺が追加されます。これによって、頂点 $1$ から頂点 $4$ に $1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 4$ とちょうど $3$ 回の移動で到達できるようになり、頂点 $4$ は良い頂点に変わります。
• 時刻 $4$ に、頂点 $3$ から頂点 $2$ への有向辺が追加されます。これによって、頂点 $1$ から頂点 $2$ に $1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 2$ とちょうど $3$ 回の移動で到達できるようになり、頂点 $2$ は良い頂点に変わります。
• 時刻 $5$ に、頂点 $2$ から頂点 $2$ への有向辺（自己ループ）が追加されます。これによって、頂点 $1$ から頂点 $3$ に $1 \\rightarrow 2 \\rightarrow 2 \\rightarrow 3$ とちょうど $3$ 回の移動で到達できるようになり、頂点 $3$ は良い頂点に変わります。

頂点 $1$ が良い頂点となることはありません。

入力例 2

2 1 1000000000
1 2

出力例 2

-1 -1