好顶点

题目描述

我们有一个包含 $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$。

输入格式

输入按以下格式从标准输入给出：

$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$，因此顶点 $4$ 成为好顶点。

在时刻 $4$，添加从顶点 $3$ 指向顶点 $2$ 的有向边。现在，从顶点 $1$ 出发恰好走三步可以到达顶点 $2$：$1 \rightarrow 2 \rightarrow 3 \rightarrow 2$，因此顶点 $2$ 成为好顶点。

在时刻 $5$，添加从顶点 $2$ 指向顶点 $2$ 的有向边（自环）。现在，从顶点 $1$ 出发恰好走三步可以到达顶点 $3$：$1 \rightarrow 2 \rightarrow 2 \rightarrow 3$，因此顶点 $3$ 成为好顶点。

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

2 1 1000000000
1 2

-1 -1

数据范围

• $2 \le N \le 100$
• $1 \le T \le N^2$
• $1 \le L \le 10^9$
• $1 \le u_t, v_t \le N$
• $i \neq j \Rightarrow (u_i, v_i) \neq (u_j, v_j)$
• 输入中的所有值均为整数。