Uma coloração com $k$ cores de um grafo não direcionado rotulado com $n$ vértices é uma atribuição de cores aos vértices tal que cada vértice recebe uma cor inteira $x$ ($1\leq x\leq k$) e quaisquer dois vértices adjacentes têm cores diferentes. Uma coloração pode ser tratada como um vetor de comprimento $n$ de inteiros de $1$ a $k$, cujo $i$-ésimo elemento corresponde à cor do $i$-ésimo vértice do grafo.

Uma coloração $b$ é monótona em relação a uma coloração $a$ do mesmo grafo se exatamente uma das seguintes afirmações for verdadeira:

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

Observe que uma coloração não é monótona em relação a si mesma, pois nesse caso ambas as afirmações acima são verdadeiras.

Você recebe um grafo não direcionado rotulado e sua coloração $a$ com $k$ cores. Existe uma coloração $b$ desse grafo com $k$ cores que seja monótona em relação a $a$?

Entrada

A primeira linha contém três inteiros $n$, $m$ e $k$ ($1\leq n,m,k\leq 3\cdot 10^5$), o número de vértices, o número de arestas e o número de cores, respectivamente.

A segunda linha contém $n$ inteiros $a_i$ ($1\leq c_i\leq k$), as cores dos vértices.

Seguem-se $m$ linhas. A $i$-ésima contém dois inteiros $u_i$ e $v_i$ ($1\leq u_i<v_i\leq n$), descrevendo uma aresta entre os vértices $u_i$ e $v_i$.

O grafo não contém laços nem arestas múltiplas. É garantido que o vetor $a$ descreve uma coloração válida do grafo dado.

Saída

Imprima $1$ se existir uma coloração $b$ monótona em relação a $a$, e imprima $0$ caso contrário.

Exemplos

Entrada 1

3 2 3
1 2 3
1 2
2 3

Saída 1

1

Entrada 2

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

Saída 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

Saída 3

0