Una coloración con $k$ colores de un grafo no dirigido etiquetado con $n$ vértices es una asignación de colores a sus vértices, de modo que cada vértice recibe un color entero $x$ ($1\leq x\leq k$) y dos vértices adyacentes nunca tienen el mismo color. Una coloración puede verse como un arreglo de longitud $n$ de enteros entre $1$ y $k$, cuyo elemento $i$ corresponde al color del vértice $i$ del grafo.

La coloración $b$ es monótona respecto a la coloración $a$ del mismo grafo si se cumple exactamente una de las siguientes afirmaciones:

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

Observa que una coloración no es monótona respecto a sí misma, porque en ese caso se cumplen ambas afirmaciones anteriores.

Se te da un grafo no dirigido etiquetado y su coloración $a$ con $k$ colores. ¿Existe una coloración $b$ del grafo dado con $k$ colores que sea monótona respecto a $a$?

Entrada

La primera línea contiene tres enteros $n$, $m$ y $k$ ($1\leq n,m,k\leq 3\cdot 10^5$), el número de vértices, el número de aristas y el número de colores, respectivamente.

La segunda línea contiene $n$ enteros $a_i$ ($1\leq c_i\leq k$), los colores de los vértices.

A continuación hay $m$ líneas. La línea $i$ contiene dos enteros $u_i$ y $v_i$ ($1\leq u_i<v_i\leq n$) que describen una arista entre los vértices $u_i$ y $v_i$.

El grafo no contiene bucles ni aristas múltiples. Se garantiza que el arreglo $a$ describe una coloración válida del grafo dado.

Salida

Imprime $1$ si existe una coloración $b$ monótona respecto a $a$ e imprime $0$ en caso contrario.

Ejemplos

Entrada 1

3 2 3
1 2 3
1 2
2 3

Salida 1

1

Entrada 2

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

Salida 2

0

Entrada 3

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

Salida 3

0