题目描述

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

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

当一个顶点可以通过从 Vertex $1$ 开始沿着一条边恰好经过 $L$ 次到达时，我们称其为 好的 顶点。

对于每个 $i = 1, 2, \ldots, N$，打印出 Vertex $i$ 成为好的顶点的最早时间。如果 Vertex $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$，打印 Vertex $i$ 成为好的顶点的最早时间 $X_i$。如果 Vertex $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$，从 Vertex $2$ 到 Vertex $3$ 添加了一条有向边。
• 在时间 $2$，从 Vertex $3$ 到 Vertex $4$ 添加了一条有向边。
• 在时间 $3$，从 Vertex $1$ 到 Vertex $2$ 添加了一条有向边。现在，Vertex $4$ 可以通过恰好三步从 Vertex $1$ 到达：$1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 4$，使得 Vertex $4$ 成为好的顶点。
• 在时间 $4$，从 Vertex $3$ 到 Vertex $2$ 添加了一条有向边。现在，Vertex $2$ 可以通过恰好三步从 Vertex $1$ 到达：$1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 2$，使得 Vertex $2$ 成为好的顶点。
• 在时间 $5$，从 Vertex $2$ 到 Vertex $2$ 添加了一条有向边（自环）。现在，Vertex $3$ 可以通过恰好三步从 Vertex $1$ 到达：$1 \\rightarrow 2 \\rightarrow 2 \\rightarrow 3$，使得 Vertex $3$ 成为好的顶点。

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

示例输入 2

2 1 1000000000
1 2

示例输出 2

-1 -1