Василий и Петр нашли числовой граф — связный ориентированный граф, в каждой вершине которого записано число.
Ребятам уже давно нужно число, то они решили сыграть в игру на графе. Они поставили фишку в вершину под номером 1. За один ход можно или закончить игру и взять число с вершины, в которой сейчас находится фишка, или передвинуть фишку в соседнюю вершину по ориентированному ребру. При этом после 10100 ходов игра автоматически заканчивается и ребята берут число с вершины, в которой на данный момент находится фишка.
Первым начинает Василий, при этом он хочет максимизировать число, а Петр минимизировать. Найдите число, которое получат ребята в конце игры, если оба ребята играют оптимально.
Первая строка содержит два целых числа n и m (1≤n≤250000,1≤m≤500000) — количество вершин и ребер графа соответственно.
Вторая строка содержит n целых чисел ai (1≤ai≤109) — числа, записанные на вершинах графа.
Последние m строк содержат по два целых числа x и y (1≤x,y≤n), означающие что существует ориентированное ребро, ведущее из x в y.
В единственной строке выведите одно целое число, которое получат ребята в конце игры, если оба играют оптимально.
На рисунке 1 изображен граф из первого примера. В вершинах записан номер вершины и число по игре в скобках.
Первый ход делает Василий, он может сразу остановить игру или пойти в вершину 2. Лучшим ходом будет пойти по ребру.
Дальше ходит Петр, ему выгодно пойти в вершину 3.
В конце, если Василий пойдет в вершину 1, то Петр закончит игру с числом 1, поэтому лучше будет сразу закончить игру с числом 4.
На рисунке 2 изображен граф со второго примера.
Здесь ребята будут по очереди ходить все 10100 шагов, пока в конце фишка не остановится в вершине 1.
(6 баллов) данный граф — прямая, в которой все ребра направлены в одну сторону;
(8 баллов) данный граф — дерево с корнем в вершине 1, в котором все ребра направлены от корня вниз;
(14 баллов) данный граф — цикл;
(26 баллов) 1≤ai≤2;
(46 баллов) без дополнительных ограничений.