当前没有测试数据。

G - 好点

得分：$600$ 分

问题描述

我们有一个有向图，有 $N$ 个顶点。 这 $N$ 个顶点分别称为顶点 $1$，顶点 $2$，$\ldots$，顶点 $N$。 在时间 $0$，该图没有边。

对于每个 $t = 1, 2, \ldots, T$，在时间 $t$，将从顶点 $u_t$ 添加一条有向边到顶点 $v_t$。（边可以是自环，即可能成立 $u_t = v_t$。）

当可以通过从顶点 $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$ 的有向边。此时，顶点 $4$ 可以通过 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ 恰好三步到达，即顶点 $4$ 成为好顶点。
• 在时间 $4$，添加一条从顶点 $3$ 到顶点 $2$ 的有向边。此时，顶点 $2$ 可以通过 $1 \rightarrow 2 \rightarrow 3 \rightarrow 2$ 恰好三步到达，即顶点 $2$ 成为好顶点。
• 在时间 $5$，添加一条从顶点 $2$ 到顶点 $2$ 的有向边（自环）。此时，顶点 $3$ 可以通过 $1 \rightarrow 2 \rightarrow 2 \rightarrow 3$ 恰好三步到达，即顶点 $3$ 成为好顶点。

顶点 $1$ 永远不会成为好顶点。

---

2 1 1000000000
1 2

-1 -1