Eine Färbung eines beschrifteten ungerichteten Graphen mit $n$ Knoten in $k$ Farben weist seinen Knoten Farben zu, sodass jeder Knoten eine ganzzahlige Farbe $x$ ($1\leq x\leq k$) erhält und keine zwei benachbarten Knoten dieselbe Farbe haben. Eine Färbung kann als Array der Länge $n$ mit ganzen Zahlen von $1$ bis $k$ aufgefasst werden, dessen $i$-tes Element der Farbe des $i$-ten Knotens entspricht.

Eine Färbung $b$ ist monoton bezüglich einer Färbung $a$ desselben Graphen, wenn genau eine der folgenden Aussagen gilt:

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

Beachte, dass eine Färbung nicht monoton bezüglich ihrer selbst ist, da dann beide obigen Aussagen gelten.

Gegeben sind ein beschrifteter ungerichteter Graph und seine Färbung $a$ mit $k$ Farben. Gibt es eine Färbung $b$ des gegebenen Graphen mit $k$ Farben, die monoton bezüglich $a$ ist?

Eingabe

Die erste Zeile enthält drei ganze Zahlen $n$, $m$ und $k$ ($1\leq n,m,k\leq 3\cdot 10^5$): die Anzahl der Knoten, der Kanten beziehungsweise der Farben.

Die zweite Zeile enthält $n$ ganze Zahlen $a_i$ ($1\leq c_i\leq k$), die Farben der Knoten.

Es folgen $m$ Zeilen. Die $i$-te enthält zwei ganze Zahlen $u_i$ und $v_i$ ($1\leq u_i<v_i\leq n$), die eine Kante zwischen den Knoten $u_i$ und $v_i$ beschreiben.

Der Graph enthält keine Schleifen oder Mehrfachkanten. Es ist garantiert, dass das Array $a$ eine gültige Färbung des gegebenen Graphen beschreibt.

Ausgabe

Gib $1$ aus, wenn eine Färbung $b$ existiert, die monoton bezüglich $a$ ist, andernfalls $0$.

Beispiele

Eingabe 1

3 2 3
1 2 3
1 2
2 3

Ausgabe 1

1

Eingabe 2

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

Ausgabe 2

0

Eingabe 3

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

Ausgabe 3

0