Раскраска помеченного неориентированного графа с $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