G - Good Vertices Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点の有向グラフがあります。N 個の頂点はそれぞれ頂点 1 、頂点 2 、\ldots、頂点 N と呼ばれます。 時刻 0 には、このグラフには辺がありません。

t = 1, 2, \ldots, T について、時刻 t に頂点 u_t から頂点 v_t への有向辺が追加されます。 （追加される辺が自己ループである場合、すなわち u_t = v_t の場合もあります。）

頂点 1 から始め「現在いる頂点からちょうど 1 本の有向辺をたどって到達できる頂点を 1 つ選び、選んだ頂点に移動する」ことをちょうど L 回繰り返して到達できる頂点を「良い頂点」と呼びます。

i = 1, 2, \ldots, N について、頂点 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 について、頂点 i が良い頂点となる最小の時刻 X_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 への有向辺が追加されます。これによって、頂点 1 から頂点 4 に 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 とちょうど 3 回の移動で到達できるようになり、頂点 4 は良い頂点に変わります。
  • 時刻 4 に、頂点 3 から頂点 2 への有向辺が追加されます。これによって、頂点 1 から頂点 2 に 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 とちょうど 3 回の移動で到達できるようになり、頂点 2 は良い頂点に変わります。
  • 時刻 5 に、頂点 2 から頂点 2 への有向辺（自己ループ）が追加されます。これによって、頂点 1 から頂点 3 に 1 \rightarrow 2 \rightarrow 2 \rightarrow 3 とちょうど 3 回の移動で到達できるようになり、頂点 3 は良い頂点に変わります。

頂点 1 が良い頂点となることはありません。

入力例 2

2 1 1000000000
1 2

出力例 2

-1 -1

Score : 600 points

Problem Statement

We have a directed graph with N vertices. The N vertices are called Vertex 1, Vertex 2, \ldots, Vertex N. At time 0, the graph has no edge.

For each t = 1, 2, \ldots, T, at time t, a directed edge from Vertex u_t to Vertex v_t will be added. (The edge may be a self-loop, that is, u_t = v_t may hold.)

A vertex is called good when it can be reached by starting at Vertex 1 and traversing an edge exactly L times.

For each i = 1, 2, \ldots, N, print the earliest time when Vertex i is good. If there is no time when Vertex i is good, print -1 instead.

Constraints

  • 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)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N T L
u_1 v_1
u_2 v_2
\vdots
u_T v_T

Output

In the following format, for each i = 1, 2, \ldots, N, print the earliest time X_i when Vertex i is good. If there is no time when Vertex i is good, X_i should be -1.

X_1 X_2 \ldots X_N

Sample Input 1

4 5 3
2 3
3 4
1 2
3 2
2 2

Sample Output 1

-1 4 5 3

At time 0, the graph has no edge. Afterward, edges are added as follows.

  • At time 1, a directed edge from Vertex 2 to Vertex 3 is added.
  • At time 2, a directed edge from Vertex 3 to Vertex 4 is added.
  • At time 3, a directed edge from Vertex 1 to Vertex 2 is added. Now, Vertex 4 can be reached from Vertex 1 in exactly three moves: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4, making Vertex 4 good.
  • At time 4, a directed edge from Vertex 3 to Vertex 2 is added. Now, Vertex 2 can be reached from Vertex 1 in exactly three moves: 1 \rightarrow 2 \rightarrow 3 \rightarrow 2, making Vertex 2 good.
  • At time 5, a directed edge (self-loop) from Vertex 2 to Vertex 2 is added. Now, Vertex 3 can be reached from Vertex 1 in exactly three moves: 1 \rightarrow 2 \rightarrow 2 \rightarrow 3, making Vertex 3 good.

Vertex 1 will never be good.

Sample Input 2

2 1 1000000000
1 2

Sample Output 2

-1 -1