Pewarnaan graf tak berarah berlabel dengan $n$ simpul menggunakan $k$ warna adalah pemberian warna pada simpul-simpulnya sehingga setiap simpul menerima warna berupa bilangan bulat $x$ ($1\leq x\leq k$) dan tidak ada dua simpul bertetangga yang berwarna sama. Pewarnaan dapat dianggap sebagai larik sepanjang $n$ berisi bilangan bulat dari $1$ hingga $k$, dengan elemen ke-$i$ menyatakan warna simpul ke-$i$ graf.

Pewarnaan $b$ monoton terhadap pewarnaan $a$ pada graf yang sama jika tepat satu dari pernyataan berikut berlaku:

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

Perhatikan bahwa suatu pewarnaan tidak monoton terhadap dirinya sendiri karena dalam hal itu kedua pernyataan di atas berlaku.

Diberikan sebuah graf tak berarah berlabel dan pewarnaannya $a$ dengan $k$ warna. Apakah ada pewarnaan $b$ graf tersebut dengan $k$ warna yang monoton terhadap $a$?

Masukan

Baris pertama berisi tiga bilangan bulat $n$, $m$, dan $k$ ($1\leq n,m,k\leq 3\cdot 10^5$), masing-masing banyaknya simpul, banyaknya sisi, dan banyaknya warna.

Baris kedua berisi $n$ bilangan bulat $a_i$ ($1\leq c_i\leq k$), warna simpul-simpulnya.

Berikutnya terdapat $m$ baris. Baris ke-$i$ berisi dua bilangan bulat $u_i$ dan $v_i$ ($1\leq u_i<v_i\leq n$), yang mendeskripsikan sebuah sisi antara simpul $u_i$ dan $v_i$.

Graf tidak memuat gelang atau sisi ganda. Dijamin larik $a$ mendeskripsikan pewarnaan yang sah dari graf yang diberikan.

Keluaran

Keluarkan $1$ jika terdapat pewarnaan $b$ yang monoton terhadap $a$, dan keluarkan $0$ jika tidak.

Contoh

Masukan 1

3 2 3
1 2 3
1 2
2 3

Keluaran 1

1

Masukan 2

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

Keluaran 2

0

Masukan 3

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

Keluaran 3

0