给定一个包含 $n$ 个顶点和 $m$ 条边的连通无向图。顶点编号为 $1$ 到 $n$。 $s$ 是初始顶点。你不知道 $s$ 的具体编号，但你知道从顶点 $s$ 到所有其他顶点（包括自身）的最短距离对 $3$ 取模后的结果。你需要找到 $s$ 的编号。 两个顶点之间的距离是它们之间最短路径的长度。路径的长度为其包含的边数。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 500\,000$)，分别表示顶点数和边数。 第二行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$ ($0 \le d_i \le 2$)。其中 $d_i$ 是顶点 $s$ 到顶点 $i$ 的距离对 $3$ 取模后的值。 接下来的 $m$ 行描述图的边。第 $i$ 行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示该边连接的两个顶点的编号。 保证图中没有自环和重边。同时保证图是连通的。

输出格式

输出 $s$ 的编号：初始顶点的索引。如果有多个答案，输出其中任意一个即可。

样例

样例输入 1

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

样例输出 1

2

样例输入 2

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

样例输出 2

1

说明

在第一个样例中，从顶点 $2$ 到所有顶点的距离数组为 $[1, 0, 1, 1, 2]$，这与给定的数组 $d$ 相等。 在第二个样例中，从顶点 $1$ 出发的距离数组为 $[0, 1, 2, 3, 2, 1]$。如果对每个元素取模 $3$，我们将得到数组 $d$。