← 返回题目列表

AtCoder · abc236_g

G. 好的顶点

中文机器翻译题面 查看原题

分数: 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