题目描述

$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$ を出力してください。

输入格式

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

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

题目大意

有一个有 $N$ 个节点的有向图，最开始没有一条边，接下来有 $T$ 次操作，第 $t$ 次加入一条 $u_t$ 到 $v_t$ 的有向边(可能存在自环)。

定义一个节点是好节点当且仅当能从 $1$ 号节点出发经过恰好 $L$ 条边到达该节点。

输出每个节点成为好节点的最少操作次数，如果不能，输出 $-1$。

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

-1 4 5 3

2 1 1000000000
1 2

-1 -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) $
• 入力はすべて整数

Sample Explanation 1

時刻 $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$ が良い頂点となることはありません。