Числовой граф

Василий и Петр нашли числовой граф — связный ориентированный граф, в каждой вершине которого записано число.

Ребятам уже давно нужно число, то они решили сыграть в игру на графе. Они поставили фишку в вершину под номером 1. За один ход можно или закончить игру и взять число с вершины, в которой сейчас находится фишка, или передвинуть фишку в соседнюю вершину по ориентированному ребру. При этом после $10^{100}$ ходов игра автоматически заканчивается и ребята берут число с вершины, в которой на данный момент находится фишка.

Первым начинает Василий, при этом он хочет максимизировать число, а Петр минимизировать. Найдите число, которое получат ребята в конце игры, если оба ребята играют оптимально.

Входные данные

Первая строка содержит два целых числа $n$ и $m$ ($1\le n\le 250000,1\le m\le 500000$) — количество вершин и ребер графа соответственно.

Вторая строка содержит $n$ целых чисел $a_i$ ($1\le a_i\le 10^9$) — числа, записанные на вершинах графа.

Последние $m$ строк содержат по два целых числа $x$ и $y$ ($1\le x,y\le n$), означающие что существует ориентированное ребро, ведущее из $x$ в $y$.

Выходные данные

В единственной строке выведите одно целое число, которое получат ребята в конце игры, если оба играют оптимально.

Примеры

Примечание

На рисунке 1 изображен граф из первого примера. В вершинах записан номер вершины и число по игре в скобках.

1. Первый ход делает Василий, он может сразу остановить игру или пойти в вершину $2$. Лучшим ходом будет пойти по ребру.

2. Дальше ходит Петр, ему выгодно пойти в вершину $3$.

3. В конце, если Василий пойдет в вершину $1$, то Петр закончит игру с числом $1$, поэтому лучше будет сразу закончить игру с числом $4$.

На рисунке $2$ изображен граф со второго примера.

Здесь ребята будут по очереди ходить все $10^{100}$ шагов, пока в конце фишка не остановится в вершине $1$.

Оценивание

1. ($6$ баллов) данный граф — прямая, в которой все ребра направлены в одну сторону;

2. ($8$ баллов) данный граф — дерево с корнем в вершине 1, в котором все ребра направлены от корня вниз;

3. ($14$ баллов) данный граф — цикл;

4. ($26$ баллов) $1\le a_i\le 2$;

5. ($46$ баллов) без дополнительных ограничений.