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

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

4 seconds
512 megabytes
Very hard

Василь і Петрик знайшли числовий граф — зв'язний орієнтований граф, на кожній вершині якого записано число.

Хлопцям вже давно потрібно число, тому вони вирішили зіграти в гру на графі. Вони поставили фішку в вершину під номером 1. За один хід можна або закінчити гру і взяти число з вершини, в якій зараз знаходиться фішка, або передвинути фішку в сусідню вершину по орієнтованому ребру. При цьому після 10^{100} ходів автоматично закінчується і хлопці беруть число з вершини, в якій зараз заходиться фішка.

Першим починає Василь, при цьому він хоче максимізувати число, а Петрик мінімізувати. Знайдіть число, яке отримають хлопці в кінці гри, якщо обидва хлопці грають оптимально.

Input

Перший рядок містить два цілі числа та (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), які означають що існує орієнтоване ребро, що веде з в .

Output

В єдиному рядку виведіть одне ціле число, яке отримають хлопці в кінці гри, якщо обидва хлопці грають оптимально.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

У першому прикладі на рисунку 1 зображено граф з першого прикладу. У вершинах записано номер вершини і число з гри в дужках.

  1. Перший хід робить Василь, він може одразу зупинити гру або піти в вершину . Кращим буде піти по ребру.

  2. Далі ходить Петрик, йому вигідно піти в вершину .

  3. В кінці, якщо Василь піде в вершину , то Петрик закінчить гру з числом , тому краще буде одразу закінчити гру з числом .

У другому прикладі на рисунку зображено граф з другого прикладу.

Тут хлопці будуть по черзі ходити всі 10^{100} кроків, поки в кінці фішка не зупиниться у вершині .

Scoring

  1. ( балів) даний граф — пряма, в якій всі ребра направлені в одну сторону;

  2. ( балів) даний граф — дерево з коренем у вершині 1, в якому всі ребра направлені від кореня до низу;

  3. ( балів) даний граф — цикл;

  4. ( балів) 1 \leq a_i \leq 2;

  5. ( балів) без додаткових обмежень.