Problem B
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. This number is either $0$ or $1$. A walk is a sequence $v_1v_2 \dots v_k$ of vertices in the graph such that any two consecutive vertices are connected by an edge. We call a binary sequence

walkable if there is a walk $v_1v_2 \dots v_k$ in the graph that satisfies $a_{v_1} a_{v_2} \dots a_{v_k} = s$.

In other words, a binary sequence is walkable if it is possible to obtain $s$ by walking in the graph and writing down the binary numbers in the order that they are visited. An example is visualized in Figure 1.

Figure 1: Illustration of Sample Input 1. Every binary sequence of length at most $3$ is walkable.

Your task is to find the length of a shortest binary sequence that is not walkable.

Input

The input consists of:

• One line with 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.

• One line with $n$ integers $a_1,\dots , a_n$ ($a_v \in \{ 0, 1\} $ for each $v$), where $a_v$ is the number written on vertex $v$.

• $m$ lines, each with two integers $u$ and $v$ ($1 \leq u,v \leq n$, $u \neq v$), denoting that the vertices $u$ and $v$ are connected by an edge. It is guaranteed that every pair of vertices is connected by at most one edge.

Output

If every binary sequence is walkable, output “infinity”. Otherwise, output the length of a shortest binary sequence that is not walkable.

4 4
0 0 1 1
1 2
1 3
2 3
3 4

4

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

infinity

1 0
0

1