У Алсу есть неориентированный граф с $$$n$$$ вершинами и $$$m$$$ рёбрами. Вершины пронумерованы целыми числами от $$$1$$$ до $$$n$$$. В каждой вершине записано число. В вершине с индексом $$$v$$$ записано число $$$c_v$$$.
Алсу называет прогулкой между вершинами $$$v_1$$$ и $$$v_k$$$ последовательность вершин $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_k$$$ такую, что вершины $$$v_i$$$ и $$$v_{i+1}$$$ связаны ребром для всех $$$1 \leq i \leq k-1$$$. Заметим, что одна и та же вершина и даже одно и то же ребро может встречаться в прогулке несколько раз.
Алсу называет медианой $$$k$$$ чисел $$$\left\lfloor\frac{k}{2}+1 \right\rfloor$$$-е по величине число ($$$1$$$-е по величине число наименьшее). Скобки $$$\lfloor \rfloor$$$ означают округление вниз до ближайшего целого.
Алсу называет медианой прогулки значение, которое равно медиане всех чисел, написанных в вершинах, встречающихся в прогулке. Заметим, что если длина прогулки $$$k$$$, то надо рассматривать именно $$$k$$$ чисел (т.е. число, записанное на какой-то вершине, необходимо рассматривать столько раз, сколько эта вершина была посещена во время прогулки).
Помогите Алсу найти минимально возможное число среди медиан всех прогулок от вершины $$$1$$$ до вершины $$$n$$$.
В первой строке находится два разделенных пробелом целых числа $$$n$$$ ($$$2 \leq n \leq 10^5$$$) b $$$m$$$ ($$$0 \leq m \leq 2 \cdot 10^5$$$), количество вершин и ребер графа. Вторая строка содержит $$$n$$$ целых чисел $$$c_1$$$, $$$\ldots$$$, $$$c_n$$$ ($$$1 \leq c_i \leq 10^9$$$). Следующие $$$m$$$ строк содержат описание ребер. $$$i$$$-я строка содержит два числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$), номер двух концов $$$i$$$-о ребра. Граф может содержать кратные ребра и петли.
Выведите единственное целое число, минимально возможное значение среди медиан всех прогулок от вершины $$$1$$$ до вершины $$$n$$$. Если между вершинами $$$1$$$ и $$$n$$$ нет пути, то выведите $$$-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
