一個有 $n$ 個頂點嘅帶標號無向圖嘅 $k$ 色染色，就係幫每個頂點分配顏色，令每個頂點得到一個整數顏色 $x$（$1\leq x\leq k$），而且任何兩個相鄰頂點嘅顏色都唔同。一個染色可以當成長度係 $n$、元素由 $1$ 到 $k$ 嘅整數陣列，第 $i$ 個元素對應圖入面第 $i$ 個頂點嘅顏色。

如果以下敘述啱啱好有一項成立，就話染色 $b$ 相對於同一個圖嘅染色 $a$ 係單調嘅：

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

留意，一個染色相對於自己唔係單調嘅，因為呢個情況下上面兩項敘述都成立。

畀定一個帶標號無向圖，同埋佢嘅 $k$ 色染色 $a$。有冇呢個圖嘅一個 $k$ 色染色 $b$，係相對於 $a$ 單調嘅？

輸入格式

第一行有三個整數 $n$、$m$ 同 $k$（$1\leq n,m,k\leq 3\cdot 10^5$），分別係圖嘅頂點數、邊數同顏色數。

第二行有 $n$ 個整數 $a_i$（$1\leq c_i\leq k$），即係各個頂點嘅顏色。

跟住有 $m$ 行。第 $i$ 行有兩個整數 $u_i$ 同 $v_i$（$1\leq u_i<v_i\leq n$），描述連接頂點 $u_i$ 同 $v_i$ 嘅一條邊。

圖入面冇自環或者重邊。保證陣列 $a$ 描述咗呢個圖嘅合法染色。

輸出格式

如果存在一個相對於 $a$ 單調嘅染色 $b$，就輸出 $1$；否則輸出 $0$。

樣例

輸入格式 1

3 2 3
1 2 3
1 2
2 3

輸出格式 1

1

輸入格式 2

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

輸出格式 2

0

輸入格式 3

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

輸出格式 3

0