정점 찾기

정점이 $n$개, 간선이 $m$개인 연결된 무방향 그래프가 주어진다. 정점은 $1$부터 $n$까지 번호가 붙어 있다. 정점 번호 $s$가 시작 정점이다. $s$의 값은 알 수 없지만, 정점 $s$에서 자기 자신을 포함한 모든 정점까지의 거리를 3으로 나눈 나머지는 알고 있다. $s$를 찾아야 한다.

두 정점 사이의 거리는 두 정점을 잇는 최단 경로의 길이이다. 경로의 길이는 경로에 포함된 간선의 개수이다.

첫째 줄에 정점의 개수 $n$과 간선의 개수 $m$이 주어진다. ($1 \le n, m \le 500\,000$)

둘째 줄에 $n$개의 정수 $d_1, d_2, \ldots, d_n$이 주어진다. ($0 \le d_i \le 2$) 여기서 $d_i$는 정점 $s$와 정점 $i$ 사이의 거리를 3으로 나눈 나머지이다.

다음 $m$개의 줄에는 간선이 주어진다. 이 중 $i$번째 줄은 $i$번째 간선을 나타내며, 간선으로 연결된 두 정점의 번호 $u$와 $v$가 주어진다. ($1 \le u, v \le n$)

그래프에 자기 간선과 중복 간선은 없다. 그래프는 연결되어 있다.

시작 정점의 번호 $s$를 출력한다. 답이 여러 개라면 그중 아무거나 하나를 출력한다.

첫 번째 예제에서 정점 2와 모든 정점 사이의 거리 배열은 $[1, 0, 1, 1, 2]$이다. 이는 주어진 배열 $d$와 같다.

두 번째 예제에서 정점 1에서 모든 정점까지의 거리 배열은 $[0, 1, 2, 3, 2, 1]$이다. 각 원소를 3으로 나눈 나머지를 구하면 배열 $d$가 된다.