Числовий граф#10450
Василь і Петрик знайшли числовий граф — зв'язний орієнтований граф, на кожній вершині якого записано число.
Хлопцям вже давно потрібно число, тому вони вирішили зіграти в гру на графі. Вони поставили фішку у вершину під номером . За один хід можна або закінчити гру і взяти число з вершини, в якій зараз перебуває фішка, або пересунути фішку в сусідню вершину по орієнтованому ребру. Після 10^{100} ходів гра автоматично закінчується, і хлопці беруть число з вершини, в якій зараз перебуває фішка.
Першим починає Василь, при цьому він хоче максимізувати число, а Петрик — мінімізувати. Знайдіть число, яке отримають хлопці в кінці гри, якщо обидва хлопці грають оптимально.
Перший рядок містить два цілі числа та (1 \leq n \leq 250\,000, 1 \leq m \leq 500\,000) — кількість вершин і ребер графу відповідно.
Другий рядок містить цілих чисел a_i (1 \leq a_i \leq 10^9) — числа, записані на вершинах графу.
Останні рядків містять по два цілі числа і (1 \leq x, y \leq n), які означають, що існує орієнтоване ребро, що веде з в .
В єдиному рядку виведіть одне ціле число, яке отримають хлопці в кінці гри, якщо обидва хлопці грають оптимально.
Приклад 1
Приклад 2
У першому прикладі на рисунку зображено граф з першого прикладу. У вершинах записано номер вершини і число з гри в дужках.
Перший хід робить Василь, він може одразу зупинити гру або піти у вершину . Краще буде піти по ребру.
Далі ходить Петрик, йому вигідно піти у вершину .
В кінці, якщо Василь піде у вершину , то Петрик закінчить гру з числом , тому краще буде одразу закінчити гру з числом .
У другому прикладі на рисунку зображено граф з другого прикладу.
Тут хлопці будуть по черзі ходити всі 10^{100} кроків, поки в кінці фішка не зупиниться у вершині .
( балів): даний граф — пряма, у якій всі ребра направлені в одну сторону;
( балів): даний граф — дерево з коренем у вершині , у якому всі ребра направлені від кореня до низу;
( балів): даний граф — цикл;
( балів): 1 \leq a_i \leq 2;
( балів): без додаткових обмежень.