配点 : $600$ 点

問題文

$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$

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

-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 1 1000000000
1 2

-1 -1