이진 탐색

무방향 그래프가 주어진다. 정점의 개수는 $n$, 간선의 개수는 $m$이다. 각 정점 $v$에는 0 또는 1인 수 $a_v$가 적혀 있다.

걷기는 그래프의 정점을 나열한 수열 $v_1v_2 \dots v_k$이며, 연속한 두 정점이 간선으로 연결되어 있어야 한다. 이진 수열 $s = s_1s_2 \dots s_k$는 $a_{v_1} a_{v_2} \dots a_{v_k} = s$를 만족하는 걷기 $v_1v_2 \dots v_k$가 존재하면 걸을 수 있는 수열이다.

다시 말해, 그래프를 따라 걸으면서 방문한 정점의 수를 순서대로 적어 $s$를 만들 수 있으면 걸을 수 있는 수열이다. 그림 B.1은 입력 예제 1을 나타내며, 길이가 3 이하인 이진 수열은 모두 걸을 수 있다.

걸을 수 없는 이진 수열 중 가장 짧은 것의 길이를 구하라.

첫 줄에 정점의 개수 $n$과 간선의 개수 $m$이 주어진다 ($1 \leq n \leq 3 \cdot 10^5$, $0 \leq m \leq 3 \cdot 10^5$).

둘째 줄에 $n$개의 정수 $a_1, \dots, a_n$이 주어진다. 각 $a_v$는 0 또는 1이다.

이어지는 $m$개의 줄에는 정수 $u$와 $v$가 주어지며 ($1 \leq u, v \leq n$, $u \neq v$), 두 정점 $u$와 $v$가 간선으로 연결되어 있음을 뜻한다. 같은 두 정점을 잇는 간선은 최대 하나이다.

모든 이진 수열을 걸을 수 있으면 "infinity"를 출력한다. 그렇지 않으면 걸을 수 없는 이진 수열 중 가장 짧은 것의 길이를 출력한다.