AT_abc236_g [ABC236G] Good Vertices

[problemUrl]: https://atcoder.jp/contests/abc236/tasks/abc236_g $ 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 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

### 制約 - $ 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) $ - 入力はすべて整数 ### Sample Explanation 1 時刻 $ 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 $ が良い頂点となることはありません。