D - Traffic Restrictions
Flavor
2
s
1024
MB
100
点
問題文
AtCoder王国には、町 $1$ から町 $N$ の $N$ 個の町と、 町 $u_i$ から 町 $v_i$ の一方通行の道路が $M$ 本あります。
AtCodeerくんは以下の $2$ 種類の行動を好きな順番で好きな回数行えます。
- $1$ 時間かけて現在いる町から直接通行可能な町に移動する。
- $1$ 時間待つ。
また、AtCodeerくんが出発してから $T$ 時間経つと、 $M$ 本の道路は全て双方向に通行可能となります。
AtCodeerくんは町 $1$ を出発してから最も速く町 $N$ に到着するよう最適な行動を行います。
AtCodeerくんが町 $N$ に何時間で到着するか求めてください。
制約
- $1 \leq N \leq 10^5$
- $1 \leq M \leq \min\left(\frac{N(N - 1)}{2}, 10^5\right)$
- $1 \leq T \leq N$
- $1 \leq u_i, v_i \leq N (1 \leq i \leq M)$
- $u_i \neq v_i (1 \leq i \leq M)$
- $i \neq j$ ならば $(u_i, v_i) \neq (u_j, v_j)$
- AtCodeerくんは町 $N$ に到着可能である。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$ $T$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
出力
答えを出力せよ。
入力例 1
4 4 1
1 2
2 4
3 2
4 3
出力例 1
2
以下の様に行動することにより $2$ 時間で町 $N$ に到着することができ、これが最短です。
- 町 $1$ を出発し、町 $2$ に向かう。
- 町 $2$ を出発し、町 $4$ に向かう。
入力例 2
4 4 1
1 2
2 3
3 4
4 1
出力例 2
2
以下の様に行動することにより $2$ 時間で町 $N$ に到着することができ、これが最短です。
- 町 $1$ で $1$ 時間待つ。このとき、道路が双方向に通行可能となる。
- 町 $1$ を出発し、町 $4$ に向かう。
入力例 3
8 10 3
1 2
2 3
2 4
3 5
4 5
5 6
6 4
6 7
7 3
7 8
出力例 3
5