D - 混雑する交差点 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は、N 個の交差点と M 本の双方向の道路からなる街に住んでいます。交差点には 1 から N までの番号が付けられており、i 番目の道路は交差点 u_i と交差点 v_i を結んでいます。なお、自分自身を結ぶ道路（自己ループ）は存在せず、同じ 2 つの交差点を結ぶ道路も高々 1 本です。

各交差点について、その交差点に接続する道路の本数を、その交差点の混雑度と呼びます。

高橋君は交差点 1 から交差点 N へ向かいたいのですが、混雑した交差点が苦手です。

高橋君の経路は、交差点の列 p_0, p_1, p_2, \ldots, p_L（L \geq 1）として表されます。ただし、p_0 = 1、p_L = N であり、各 j = 0, 1, \ldots, L-1 について交差点 p_j と交差点 p_{j+1} を結ぶ道路が存在しなければなりません。同じ交差点や同じ道路を複数回通ることも許されます。

この経路でかかる時間（分）は、以下の 2 つの合計です。

  1. 道路の移動時間： 経路中で道路を通る回数、すなわち L 分。各道路を通るのにちょうど 1 分かかり、同じ道路を複数回通る場合はその回数分だけ数えます。
  2. 交差点の通過時間： 経路の最初の要素 p_0 と最後の要素 p_L を除いた、p_1, p_2, \ldots, p_{L-1} のそれぞれについて、その交差点の混雑度が K 以上であれば追加で 1 分かかります。これは信号待ちや人混みによるものです。同じ交差点が p_1, p_2, \ldots, p_{L-1} の中に複数回現れる場合は、現れるたびにそれぞれ判定し、該当すればその回数分だけ加算します。

通過時間の判定対象外となるのは、あくまで経路の最初の要素 p_0 と最後の要素 p_L としての出現のみです。たとえば交差点 1 や交差点 N であっても、p_1, p_2, \ldots, p_{L-1} のいずれかとして現れた場合は通過時間の対象となります。

高橋君が交差点 1 から交差点 N へ移動するとき、かかる時間の最小値を求めてください。交差点 1 から交差点 N へたどり着ける経路が存在しない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i
  • 同じ 2 つの交差点を結ぶ道路は高々 1 本である
  • 入力はすべて整数である

入力

N M K
u_1 v_1
u_2 v_2
\vdots
u_M v_M
  • 1 行目には、交差点の数 N、道路の数 M、混雑度の閾値 K が、スペース区切りで与えられる。
  • 続く M 行のうち i 行目には、i 番目の道路が結ぶ 2 つの交差点の番号 u_i, v_i が、スペース区切りで与えられる。

出力

高橋君が交差点 1 から交差点 N へ移動するのにかかる最小の時間（分）を 1 行で出力せよ。たどり着ける経路が存在しない場合は -1 を出力せよ。

入力例 1

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

出力例 1

3

入力例 2

4 2 2
1 2
3 4

出力例 2

-1

入力例 3

8 12 4
1 2
1 3
2 3
2 4
3 5
4 5
4 6
5 6
5 7
6 8
7 8
3 4

出力例 3

5

Score : 400 pts

Problem Statement

Takahashi lives in a city consisting of N intersections and M bidirectional roads. The intersections are numbered from 1 to N, and the i-th road connects intersection u_i and intersection v_i. There are no self-loops (roads connecting an intersection to itself), and there is at most one road connecting any pair of intersections.

For each intersection, the number of roads connected to that intersection is called the congestion level of that intersection.

Takahashi wants to travel from intersection 1 to intersection N, but he dislikes congested intersections.

Takahashi's route is represented as a sequence of intersections p_0, p_1, p_2, \ldots, p_L (L \geq 1), where p_0 = 1, p_L = N, and for each j = 0, 1, \ldots, L-1, there must exist a road connecting intersection p_j and intersection p_{j+1}. It is allowed to pass through the same intersection or the same road multiple times.

The time (in minutes) required for this route is the sum of the following two components:

  1. Road travel time: The number of times roads are traversed along the route, namely L minutes. Each road traversal takes exactly 1 minute, and if the same road is traversed multiple times, each traversal is counted.
  2. Intersection passing time: For each of p_1, p_2, \ldots, p_{L-1} (excluding the first element p_0 and the last element p_L of the route), if the congestion level of that intersection is K or more, an additional 1 minute is incurred. This is due to waiting at traffic lights or navigating through crowds. If the same intersection appears multiple times among p_1, p_2, \ldots, p_{L-1}, the check is performed for each occurrence, and the additional time is added for each qualifying occurrence.

Only the occurrences as the first element p_0 and the last element p_L of the route are exempt from the passing time check. For example, even intersections 1 or N, if they appear as any of p_1, p_2, \ldots, p_{L-1}, are subject to the passing time check.

Find the minimum time required for Takahashi to travel from intersection 1 to intersection N. If no route from intersection 1 to intersection N exists, output -1.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i
  • There is at most one road connecting any pair of intersections
  • All input values are integers

Input

N M K
u_1 v_1
u_2 v_2
\vdots
u_M v_M
  • The first line contains the number of intersections N, the number of roads M, and the congestion level threshold K, separated by spaces.
  • The i-th of the following M lines contains the numbers u_i and v_i of the two intersections connected by the i-th road, separated by spaces.

Output

Output in one line the minimum time (in minutes) required for Takahashi to travel from intersection 1 to intersection N. If no such route exists, output -1.

Sample Input 1

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

Sample Output 1

3

Sample Input 2

4 2 2
1 2
3 4

Sample Output 2

-1

Sample Input 3

8 12 4
1 2
1 3
2 3
2 4
3 5
4 5
4 6
5 6
5 7
6 8
7 8
3 4

Sample Output 3

5