Minimizing the Maximum Height in a Hiking Route

Helen is hiking with her friends in a highland. They plan to hike from their camp A to a beautiful showplace B. Unfortunately, Helen started feeling dizzy due to altitude sickness. Help her group find a route from A to B such that the topmost height on that route is as small as possible.

More formally, you are given an undirected graph with n vertices and m edges. Each vertex i has an associated height h_i. You are also given two distinct vertices A and B. A route is a sequence of vertices such that consecutive vertices share an edge. Let the cost of a route be:

$$cost=\max\{h_{\text{vertex}} : \text{vertex is in the route}\}.$$

Your task is to choose a route from A to B that minimizes the value of cost. If there is no valid route from A to B, output -1.

inputFormat

The first line contains two integers n and m representing the number of vertices and edges, respectively.

The second line contains two integers A and B (1-indexed) denoting the starting vertex and destination vertex.

The third line contains n integers h₁, h₂, \ldots, h_n where h_i is the height of vertex i.

Each of the next m lines contains two integers u and v indicating there is an undirected edge between vertices u and v.

outputFormat

Output a single integer representing the minimum possible value of the maximum height on any path from A to B. If no such path exists, output -1.

sample

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

2