对一个含有 $n$ 个顶点的带标号无向图进行 $k$ 种颜色的着色，是指为每个顶点分配一个整数颜色 $x$（$1 \le x \le k$），使得任意两个相邻的顶点颜色都不同。着色方案可以看作一个长度为 $n$、元素取值在 $1$ 到 $k$ 之间的整数数组，其中第 $i$ 个元素对应图的第 $i$ 个顶点的颜色。

如果对于同一个图的两种着色方案 $a$ 和 $b$，恰好满足以下两个条件之一，则称着色方案 $b$ 单调于（monotonic to）着色方案 $a$：

1. $\forall_{1 \le i \le n} a_i \le b_i$
2. $\forall_{1 \le i \le n} a_i \ge b_i$

注意，着色方案对于其自身不是单调的，因为在这种情况下上述两个条件同时成立。

给定一个带标号的无向图及其使用 $k$ 种颜色的着色方案 $a$。是否存在该图的另一种使用 $k$ 种颜色的着色方案 $b$，使得 $b$ 单调于 $a$？

输入格式

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m, k \le 3 \cdot 10^5$），分别表示图的顶点数、边数和颜色数。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le k$），表示顶点的颜色。

接下来 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i < v_i \le 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