链接：https://vjudge.net/problem/Baekjoon-18668

题目描述

给你一个连通的无向图，图中有 $n$ 个顶点和 $m$ 条边，顶点编号从 $1$ 到 $n$。某个顶点 $s$ 是起始点，但你不知道 $s$ 是哪个。你只知道从 $s$ 到所有顶点（包括它自己）的距离对 $3$ 取模后的结果。你的任务是找出这个起始顶点 $s$。 这里的距离指的是两个顶点间最短路径的长度，路径长度就是路径上边的数量。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 500000$），分别表示顶点数和边数。 第二行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$（$0 \leq d_i \leq 2$），其中 $d_i$ 表示从起始点 $s$ 到顶点 $i$ 的距离对 $3$ 取模的结果。 接下来 $m$ 行，每行两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示顶点 $u$ 和顶点 $v$ 之间有一条无向边。 保证图中没有自环和重边，且图是连通的。

输出格式

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

样例 1

Input

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

Output

2

样例 2

Input

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

Output

1

提示

在第一个样例中，顶点 $2$ 到所有顶点的距离数组是 $[1,0,1,1,2]$，正好和给定的数组 $d$ 一致。 在第二个样例中，顶点 $1$ 到所有顶点的距离是 $[0,1,2,3,2,1]$，对每个元素取模 $3$ 后得到的数组就是 $d$。

完全没有思路qwq.