Une coloration en $k$ couleurs d’un graphe non orienté étiqueté à $n$ sommets est une attribution de couleurs à ses sommets telle que chaque sommet reçoive une couleur entière $x$ ($1\leq x\leq k$) et que deux sommets adjacents n’aient jamais la même couleur. Une coloration peut être vue comme un tableau de longueur $n$ d’entiers de $1$ à $k$, dont le $i$-ième élément correspond à la couleur du $i$-ième sommet du graphe.

La coloration $b$ est monotone par rapport à la coloration $a$ du même graphe si exactement une des affirmations suivantes est vraie :

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

Notez qu’une coloration n’est pas monotone par rapport à elle-même, car dans ce cas les deux affirmations ci-dessus sont vraies.

On vous donne un graphe non orienté étiqueté et sa coloration $a$ en $k$ couleurs. Existe-t-il une coloration $b$ de ce graphe en $k$ couleurs qui soit monotone par rapport à $a$ ?

Entrée

La première ligne contient trois entiers $n$, $m$ et $k$ ($1\leq n,m,k\leq 3\cdot 10^5$), respectivement le nombre de sommets, le nombre d’arêtes et le nombre de couleurs.

La deuxième ligne contient $n$ entiers $a_i$ ($1\leq c_i\leq k$), les couleurs des sommets.

Puis suivent $m$ lignes. La $i$-ième contient deux entiers $u_i$ et $v_i$ ($1\leq u_i<v_i\leq n$), décrivant une arête entre les sommets $u_i$ et $v_i$.

Le graphe ne contient ni boucles ni arêtes multiples. Il est garanti que le tableau $a$ décrit une coloration valide du graphe donné.

Sortie

Affichez $1$ s’il existe une coloration $b$ monotone par rapport à $a$, et $0$ sinon.

Exemples

Entrée 1

3 2 3
1 2 3
1 2
2 3

Sortie 1

1

Entrée 2

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

Sortie 2

0

Entrée 3

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

Sortie 3

0