具有 $n$ 個頂點的帶標號無向圖的 $k$ 色染色，是為各頂點指派顏色，使每個頂點獲得整數顏色 $x$（$1\leq x\leq k$），且任意相鄰頂點的顏色不同。一個染色可以視為長度為 $n$、元素為 $1$ 到 $k$ 的整數的陣列，其中第 $i$ 個元素對應圖中第 $i$ 個頂點的顏色。
若以下敘述恰好有一項成立，則稱染色 $b$ 相對於同一張圖的染色 $a$ 是單調的：
- $\forall_{1\leq i\leq n}\ a_i\leq b_i$
- $\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