D - 登山ルートの選択 解説 /

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

配点 : 400 点

問題文

高橋君は、山岳地帯のハイキングコースを計画しています。この山岳地帯には N 個の地点があり、各地点には 1 から N までの番号が付けられています。地点同士は M 本の双方向の登山道で結ばれています。ただし、すべての地点間が登山道で行き来できるとは限りません。

各地点 i (1 \leq i \leq N) には標高 H_i が設定されています。

高橋君は、地点 1 （登山口）から出発し、地点 N （山頂の展望台）に到達するルートを選びたいと考えています。ここで、ルートとは地点の列 p_1, p_2, \ldots, p_L であって、以下の条件をすべて満たすものを指します。

  • p_1 = 1 かつ p_L = N である。
  • すべての 1 \leq k \leq L-1 について、地点 p_k と地点 p_{k+1} を結ぶ登山道が存在する。
  • p_1, p_2, \ldots, p_L はすべて異なる（同じ地点を 2 度以上通らない）。

ルートに含まれる地点の個数 L を、そのルートの通過地点数と呼びます。通過地点数には出発地点 1 と到着地点 N の両方を含みます。上記の条件より、L \geq 2 です。

また、ルート上で通過するすべての地点の標高の最大値、すなわち \max(H_{p_1}, H_{p_2}, \ldots, H_{p_L}) を、そのルートの最高標高と呼びます。

ルートの最高標高が大きいほど、高山病のリスクが高まります。高橋君はできるだけ高山病のリスクを抑えたいと考えています。一方で、通過する地点が多いルートを選ぶと体力が持ちません。そこで高橋君は、通過地点数 L が K 以下であるルートの中から選ぶことにしました。

通過地点数が K 以下であるルートの中で、最高標高として達成できる最小の値を求めてください。

条件を満たすルートが存在しない場合（地点 1 から地点 N に通過地点数 K 以下で到達できない場合）は -1 を出力してください。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 2 \leq K \leq N
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
  • 同じ地点の組を結ぶ登山道は高々 1 本である（多重辺はない）
  • 自己ループはない
  • グラフは連結とは限らない
  • 入力はすべて整数である

入力

N M K
H_1 H_2 \ldots H_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 1 行目には、地点の数 N 、登山道の数 M 、通過地点数の上限 K が、スペース区切りで与えられる。
  • 2 行目には、各地点の標高 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。
  • 続く M 行のうち j 行目 (1 \leq j \leq M) には、j 番目の登山道が結ぶ 2 つの地点 U_j と V_j がスペース区切りで与えられる。

出力

条件を満たすルートが存在する場合、最高標高として達成可能な最小の値を 1 行で出力せよ。条件を満たすルートが存在しない場合は -1 を出力せよ。

入力例 1

5 6 4
10 50 30 20 40
1 2
2 3
3 5
1 4
4 5
2 5

出力例 1

40

入力例 2

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

出力例 2

-1

入力例 3

8 10 5
5 100 3 7 200 4 8 6
1 2
1 3
2 5
3 4
4 6
6 7
7 8
5 8
2 8
3 7

出力例 3

8

入力例 4

10 15 4
10 500 20 15 300 25 12 8 400 30
1 2
1 3
1 7
2 5
3 4
4 6
6 10
7 8
8 10
5 10
2 10
3 10
4 10
7 10
9 10

出力例 4

30

入力例 5

2 1 2
1000000000 1
1 2

出力例 5

1000000000

Score : 400 pts

Problem Statement

Takahashi is planning a hiking course in a mountainous area. This mountainous area has N locations, each numbered from 1 to N. The locations are connected by M bidirectional mountain trails. However, it is not guaranteed that all locations are reachable from each other via trails.

Each location i (1 \leq i \leq N) has an elevation H_i.

Takahashi wants to choose a route starting from location 1 (the trailhead) and reaching location N (the summit observation deck). Here, a route is a sequence of locations p_1, p_2, \ldots, p_L that satisfies all of the following conditions:

  • p_1 = 1 and p_L = N.
  • For all 1 \leq k \leq L-1, there exists a mountain trail connecting location p_k and location p_{k+1}.
  • p_1, p_2, \ldots, p_L are all distinct (no location is visited more than once).

The number of locations L included in a route is called the number of waypoints of that route. The number of waypoints includes both the starting location 1 and the destination location N. From the above conditions, L \geq 2.

Additionally, the maximum elevation among all locations visited along the route, namely \max(H_{p_1}, H_{p_2}, \ldots, H_{p_L}), is called the maximum elevation of that route.

The higher the maximum elevation of a route, the greater the risk of altitude sickness. Takahashi wants to minimize the risk of altitude sickness as much as possible. On the other hand, choosing a route that passes through many locations will exhaust his stamina. Therefore, Takahashi has decided to choose from routes whose number of waypoints L is at most K.

Among all routes with a number of waypoints at most K, find the minimum achievable maximum elevation.

If no valid route exists (i.e., it is impossible to reach location N from location 1 with at most K waypoints), output -1.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 2 \leq K \leq N
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
  • There is at most one trail connecting any pair of locations (no multi-edges)
  • There are no self-loops
  • The graph is not necessarily connected
  • All input values are integers

Input

N M K
H_1 H_2 \ldots H_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • The first line contains the number of locations N, the number of trails M, and the upper limit on the number of waypoints K, separated by spaces.
  • The second line contains the elevations of each location H_1, H_2, \ldots, H_N, separated by spaces.
  • In the following M lines, the j-th line (1 \leq j \leq M) contains the two locations U_j and V_j connected by the j-th trail, separated by spaces.

Output

If a valid route exists, output the minimum achievable maximum elevation in one line. If no valid route exists, output -1.

Sample Input 1

5 6 4
10 50 30 20 40
1 2
2 3
3 5
1 4
4 5
2 5

Sample Output 1

40

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

8 10 5
5 100 3 7 200 4 8 6
1 2
1 3
2 5
3 4
4 6
6 7
7 8
5 8
2 8
3 7

Sample Output 3

8

Sample Input 4

10 15 4
10 500 20 15 300 25 12 8 400 30
1 2
1 3
1 7
2 5
3 4
4 6
6 10
7 8
8 10
5 10
2 10
3 10
4 10
7 10
9 10

Sample Output 4

30

Sample Input 5

2 1 2
1000000000 1
1 2

Sample Output 5

1000000000