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

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

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

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

Input

Перший рядок містить два цілі числа $n$ та $m$ ($1\le n\le 250000,1\le m\le 500000$) — кількість вершин і ребер графу відповідно.

Другий рядок містить $n$ цілих чисел $a_i$ ($1\le a_i\le 10^9$) — числа, записані на вершинах графу.

Останні $m$ рядків містять по два цілі числа $x$ і $y$ ($1\le x,y\le n$), які означають що існує орієнтоване ребро, що веде з $x$ в $y$.

Output

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

Examples

Note

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

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

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

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

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

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

Scoring

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

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

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

4. ($26$ балів) $1\le a_i\le 2$;

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