Розфарбування позначеного неорієнтованого графа з $n$ вершинами в $k$ кольорів — це призначення кольорів його вершинам так, що кожна вершина отримує цілий колір $x$ ($1\leq x\leq k$) і жодні дві суміжні вершини не мають однакового кольору. Розфарбування можна розглядати як масив довжини $n$ із цілих чисел від $1$ до $k$, у якому $i$-й елемент відповідає кольору $i$-ї вершини графа.

Розфарбування $b$ монотонне відносно розфарбування $a$ того самого графа, якщо виконується рівно одне з таких тверджень:

1. $\forall_{1\leq i\leq n}\ a_i\leq b_i$
2. $\forall_{1\leq i\leq n}\ a_i\geq b_i$

Зауважте, що розфарбування не є монотонним відносно самого себе, оскільки тоді виконуються обидва наведені твердження.

Дано позначений неорієнтований граф та його розфарбування $a$ в $k$ кольорів. Чи існує розфарбування $b$ цього графа в $k$ кольорів, монотонне відносно $a$?

Вхідні дані

Перший рядок містить три цілі числа $n$, $m$ і $k$ ($1\leq n,m,k\leq 3\cdot 10^5$) — кількість вершин, кількість ребер і кількість кольорів відповідно.

Другий рядок містить $n$ цілих чисел $a_i$ ($1\leq c_i\leq k$) — кольори вершин.

Далі йдуть $m$ рядків. $i$-й із них містить два цілі числа $u_i$ та $v_i$ ($1\leq u_i<v_i\leq n$), що описують ребро між вершинами $u_i$ та $v_i$.

Граф не містить петель чи кратних ребер. Гарантується, що масив $a$ описує правильне розфарбування заданого графа.

Вихідні дані

Виведіть $1$, якщо існує розфарбування $b$, монотонне відносно $a$, і $0$ інакше.

Приклади

Вхідні дані 1

3 2 3
1 2 3
1 2
2 3

Вихідні дані 1

1

Вхідні дані 2

3 3 3
1 2 3
1 2
2 3
1 3

Вихідні дані 2

0

Вхідні дані 3

6 6 3
1 2 3 1 2 3
4 5
1 2
2 3
3 4
1 6
5 6

Вихідні дані 3

0