407639: GYM102862 C Median Walk

You are given an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. The vertices are numbered by integers from $$$1$$$ to $$$n$$$. Each vertex has a value written in it; the value in the vertex $$$v$$$ is equal to $$$c_v$$$.

A walk between two vertices $$$v_1$$$ and $$$v_k$$$ is defined as a sequence of vertices $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_k$$$ such that the vertices $$$v_i$$$ and $$$v_{i+1}$$$ are connected by an edge for all $$$1 \leq i \leq k-1$$$. Note that the same vertex and even the same edge can occur multiple times in a walk.

We define the median of $$$k$$$ numbers to be the $$$\left\lfloor\frac{k}{2}+1 \right\rfloor$$$-th largest number (the $$$1$$$-st largest number is the smallest). The brackets $$$\lfloor \rfloor$$$ denote rounding the number to the highest integer not exceeding it. For this task, we define the value of a walk to be the median value of the values of all vertices in the walk. Note that if the walk has length $$$k$$$, you should consider $$$k$$$ numbers (that is, you should consider each vertex as many times as it is visited).

Find the smallest possible value of a walk between vertices $$$1$$$ and $$$n$$$!

The first line contains two integers $$$n$$$ ($$$2 \leq n \leq 10^5$$$) and $$$m$$$ ($$$0 \leq m \leq 10^5$$$), the number of vertices and edges in the graph. Then $$$n$$$ integers follow, the values $$$c_1$$$, $$$\ldots$$$, $$$c_n$$$ ($$$1 \leq c_i \leq 10^9$$$). The next $$$m$$$ lines contain the description of the edges, the $$$i$$$-th of these lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$), the numbers of the endpoints of the $$$i$$$-th edge. The given graph can contain multiple edges and self-loops.

Output a single integer, the minimum possible value of a walk between the vertices $$$1$$$ and $$$n$$$. If no path exists between vertices $$$1$$$ and $$$n$$$, output $$$-1$$$.

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

3

3 3
1 2 3
1 2
2 1
3 3

-1