Василь і Петрик знайшли числовий граф — зв'язний орієнтований граф, на кожній вершині якого записано число.
Хлопцям вже давно потрібно число, тому вони вирішили зіграти в гру на графі. Вони поставили фішку в вершину під номером 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 балів) без додаткових обмежень.