$n$ 頂点のラベル付き無向グラフの $k$ 色彩色とは、各頂点に整数の色 $x$（$1\leq x\leq k$）を割り当て、隣接するどの二頂点も同じ色にならないようにすることです。彩色は、$1$ から $k$ の整数からなる長さ $n$ の配列とみなせ、その第 $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