Задачи
Числовой граф
Числовой граф
Василий и Петр нашли числовой граф~--- связный ориентированный граф, в каждой вершине которого записано число.
Ребятам уже давно нужно число, то они решили сыграть в игру на графе. Они поставили фишку в вершину под номером 1. За один ход можно или закончить игру и взять число с вершины, в которой сейчас находится фишка, или передвинуть фишку в соседнюю вершину по ориентированному ребру. При этом после $10^{100}$ ходов игра автоматически заканчивается и ребята берут число с вершины, в которой на данный момент находится фишка.
Первым начинает Василий, при этом он хочет максимизировать число, а Петр минимизировать. Найдите число, которое получат ребята в конце игры, если оба ребята играют оптимально.
\InputFile
Первая строка содержит два целых числа $n$ и $m$ ($1 \leq n \leq 250\,000, 1 \leq m \leq 500\,000$)~--- количество вершин и ребер графа соответственно.
Вторая строка содержит $n$ целых чисел $a_i$ ($1 \leq a_i \leq 10^9$)~--- числа, записанные на вершинах графа.
Последние $m$ строк содержат по два целых числа $x$ и $y$ ($1 \leq x, y \leq n$), означающие что существует ориентированное ребро, ведущее из $x$ в $y$.
\OutputFile
В единственной строке выведите одно целое число, которое получат ребята в конце игры, если оба играют оптимально.
\Note
На рисунке 1 изображен граф из первого примера. В вершинах записан номер вершины и число по игре в скобках.
\begin{enumerate}
\item Первый ход делает Василий, он может сразу остановить игру или пойти в вершину $2$. Лучшим ходом будет пойти по ребру.
\item Дальше ходит Петр, ему выгодно пойти в вершину $3$.
\item В конце, если Василий пойдет в вершину $1$, то Петр закончит игру с числом $1$, поэтому лучше будет сразу закончить игру с числом $4$.
\end{enumerate}
На рисунке $2$ изображен граф со второго примера.
Здесь ребята будут по очереди ходить все $10^{100}$ шагов, пока в конце фишка не остановится в вершине $1$.
\begin {center}
\includegraphics{https://static.e-olymp.com/content/3a/3a47ab2087da5fbaa68c1c3999f4fa03e3bc1db8.png}
\includegraphics{https://static.e-olymp.com/content/82/8232a8aafdfe925a65d75ab3be72697c6cf83018.png}
\end {center}
\Scoring
\begin{enumerate}
\item ($6$ баллов) данный граф~--- прямая, в которой все ребра направлены в одну сторону;
\item ($8$ баллов) данный граф~--- дерево с корнем в вершине 1, в котором все ребра направлены от корня вниз;
\item ($14$ баллов) данный граф~--- цикл;
\item ($26$ баллов) $1 \leq a_i \leq 2$;
\item ($46$ баллов) без дополнительных ограничений.
\end{enumerate}
Входные данные #1
4 4 1 10 4 5 1 2 2 3 2 4 3 1
Выходные данные #1
4
Входные данные #2
2 2 1 2 1 2 2 1
Выходные данные #2
1