Kolorowanie etykietowanego grafu nieskierowanego o $n$ wierzchołkach za pomocą $k$ kolorów to przypisanie kolorów wierzchołkom tak, aby każdy wierzchołek otrzymał całkowity kolor $x$ ($1\leq x\leq k$), a żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Kolorowanie można traktować jako tablicę długości $n$ złożoną z liczb całkowitych od $1$ do $k$, której $i$-ty element odpowiada kolorowi $i$-tego wierzchołka grafu.

Kolorowanie $b$ jest monotoniczne względem kolorowania $a$ tego samego grafu, jeśli zachodzi dokładnie jedno z poniższych stwierdzeń:

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

Zauważ, że kolorowanie nie jest monotoniczne względem samego siebie, ponieważ wówczas zachodzą oba powyższe stwierdzenia.

Dany jest etykietowany graf nieskierowany i jego kolorowanie $a$ za pomocą $k$ kolorów. Czy istnieje kolorowanie $b$ tego grafu za pomocą $k$ kolorów, które jest monotoniczne względem $a$?

Wejście

Pierwszy wiersz zawiera trzy liczby całkowite $n$, $m$ i $k$ ($1\leq n,m,k\leq 3\cdot 10^5$), odpowiednio liczbę wierzchołków, liczbę krawędzi i liczbę kolorów.

Drugi wiersz zawiera $n$ liczb całkowitych $a_i$ ($1\leq c_i\leq k$), kolory wierzchołków.

Dalej następuje $m$ wierszy. $i$-ty z nich zawiera dwie liczby całkowite $u_i$ i $v_i$ ($1\leq u_i<v_i\leq n$), opisujące krawędź między wierzchołkami $u_i$ i $v_i$.

Graf nie zawiera pętli ani krawędzi wielokrotnych. Gwarantuje się, że tablica $a$ opisuje poprawne kolorowanie danego grafu.

Wyjście

Wypisz $1$, jeśli istnieje kolorowanie $b$ monotoniczne względem $a$, a w przeciwnym przypadku wypisz $0$.

Przykład

Wejście 1

3 2 3
1 2 3
1 2
2 3

Wyjście 1

1

Wejście 2

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

Wyjście 2

0

Wejście 3

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

Wyjście 3

0