Good Vertices

题目描述

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

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)$ 输入中的所有数值均为整数。在时间 $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$ 将永远不会成为良好。

标签: AtCoder|abc236G

来源

AtCoder|abc236G