베를란디아의 주택

베를란디아의 수도에는 교차로가 $n$개 있다. 그중 일부에는 주택이 있다. 모든 $1 \le i \le n$에 대해 $a_i$를 교차로 $i$에 있는 주택에 사는 가족의 인원 수라고 하자. $a_i$가 0이면 교차로 $i$에는 주택이 없다.

일부 교차로는 도로로 연결되어 있다. 베를란디아에는 도로가 $m$개 있다. 각 도로는 양방향으로 다닐 수 있다. 각 도로는 서로 다른 두 교차로를 잇고, 두 교차로를 직접 잇는 도로는 많아야 하나다. 어느 교차로에서든 도로를 따라 다른 모든 교차로에 갈 수 있다. 교차로 $i$와 $j$ 사이의 거리는 $i$에서 $j$까지 가는 경로에서 지나는 도로의 최소 개수이다.

한 가족이 다른 가족을 방문하면, 각 사람은 상대 가족의 사람 한 명과 짝을 이뤄 둘이 대화한다. 짝을 찾지 못한 사람이 한 명이라도 있으면 두 가족의 방문은 지루하다.

이유는 알 수 없지만, 베를란디아 정부는 $v$번 주택의 가족이 $u$번 주택의 가족을 방문하면 지루해지는 두 주택 $v$와 $u$를 찾아 달라고 요청한다. 즉 $a_v > 0$, $a_u > 0$, $a_v \ne a_u$이고 $v$에서 $u$까지의 거리가 최소여야 한다. 인원 수가 서로 다른 주택이 두 개 이상 있다는 것은 보장된다.

첫 줄에 교차로의 수 $n$과 도로의 수 $m$이 주어진다 ($2 \le n \le 1000000$, $1 \le m \le 1000000$).

둘째 줄에 $n$개의 정수 $a_i$가 주어진다 ($0 \le a_i \le 10^9$).

이어지는 $m$개의 줄에는 $i$번째 도로가 잇는 두 교차로 $v_i$와 $u_i$가 주어진다 ($1 \le v_i, u_i \le n$, $v_i \ne u_i$).

인원 수가 서로 다른 두 주택 사이의 최소 거리를 정수 하나로 출력한다.

첫 번째 예시에서는 교차로 1번과 3번에만 주택이 있고, 두 주택의 인원 수가 다르다. 두 주택 사이의 거리는 2이며, 최단 경로는 도로 1번과 2번을 사용한다.