分数: 600 点
问题陈述
我们有一个有向图 N 顶点。 的 N 顶点称为 Vertex 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,打印Vertex最早出现的时间 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,打印最早时间 X_i 当顶点 i 很好。如果没有时间当顶点 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,来自顶点的有向边 2 到顶点 将添加 3 。 添加了
- 时间 2,来自顶点的有向边 3 到顶点 将添加 4 。 添加了
- 时间 3,来自顶点的有向边 1 到顶点 将添加 2 。现在,顶点 可以从 Vertex 到达 4 可以从顶点到达 1 只需三步: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4,制作顶点 4 好。
- 时间 4,来自顶点的有向边 3 到顶点 将添加 2 。现在,顶点 可以从 Vertex 到达 2 可以从顶点到达 1 只需三步: 1 \rightarrow 2 \rightarrow 3 \rightarrow 2,制作顶点 2 好。
- 时间 5,来自 Vertex 的有向边(自循环) 2 到顶点 将添加 2 。现在,顶点 可以从 Vertex 到达 3 可以从顶点到达 1 只需三步: 1 \rightarrow 2 \rightarrow 2 \rightarrow 3,制作顶点 3 好。
顶点 1 永远不会好。
示例输入 2
2 1 1000000000 1 2
示例输出 2
-1 -1