e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Olympiad in Informatics, IV Stage, I Round

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

Василий и Петр нашли числовой граф~--- связный ориентированный граф, в каждой вершине которого записано число. Ребятам уже давно нужно число, то они решили сыграть в игру на графе. Они поставили фишку в вершину под номером 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}
Time limit 4 seconds
Memory limit 512 MiB
Input example #1
4 4
1 10 4 5
1 2
2 3
2 4
3 1
Output example #1
4
Input example #2
2 2
1 2
1 2
2 1
Output example #2
1
Author Nazarii Denga
Source 2021 Ukrainian Olympiad in Informatics, Stage IV, Round I