Binary Search

You are given an undirected graph with $n$ vertices and $m$ edges. Each vertex $v$ has a number $a_v$ written on it, which is either $0$ or $1$.

A walk is a sequence of vertices $v_1v_2 \dots v_k$ in the graph such that any two consecutive vertices are connected by an edge. A binary sequence $s = s_1s_2 \dots s_k$ is walkable if there is a walk $v_1v_2 \dots v_k$ with $a_{v_1} a_{v_2} \dots a_{v_k} = s$.

In other words, a binary sequence is walkable if you can walk through the graph and write down the numbers of the visited vertices in order to get $s$. Figure B.1 shows Sample Input 1, where every binary sequence of length at most $3$ is walkable.

Find the length of a shortest binary sequence that is not walkable.

The first line has two integers $n$ and $m$ ($1 \leq n \leq 3 \cdot 10^5$, $0 \leq m \leq 3 \cdot 10^5$), the number of vertices and the number of edges.

The second line has $n$ integers $a_1, \dots, a_n$, where each $a_v$ is either 0 or 1.

Each of the next $m$ lines has two integers $u$ and $v$ ($1 \leq u, v \leq n$, $u \neq v$), meaning vertices $u$ and $v$ are connected by an edge. Every pair of vertices is connected by at most one edge.

If every binary sequence is walkable, print "infinity". Otherwise, print the length of a shortest binary sequence that is not walkable.