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_1 v_2 \dots v_k$ in the graph such that there is an edge between every two consecutive vertices in the sequence.

A binary sequence $s = s_1 s_2 \dots s_k$ is called walkable if and only if there exists a walk $v_1 v_2 \dots v_k$ in the graph such that the sequence of numbers on these vertices matches $s$, i.e., $a_{v_1} a_{v_2} \dots a_{v_k} = s$. In other words, a binary sequence is walkable if you can traverse the graph and record the numbers on the vertices in order to obtain that binary sequence.

An example is shown in the figure below.

In this example, any binary sequence of length at most 3 is walkable.

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

Input

The input contains:

• The first line contains two integers $n$ and $m$ ($1 \leq n \leq 3 \cdot 10^5$, $0 \leq m \leq 3 \cdot 10^5$), representing the number of vertices and edges in the graph, respectively.
• The second line contains $n$ integers $a_1, a_2, \dots, a_n$ (where each $a_v \in \{0, 1\}$), representing the number on each vertex $v$.
• The next $m$ lines each contain two integers $u$ and $v$ ($1 \leq u, v \leq n$, $u \neq v$), representing an edge between vertex $u$ and vertex $v$. It is guaranteed that there is at most one edge between any two vertices.

Output

If all binary sequences are walkable, output "infinity".

Otherwise, output the length of the shortest binary sequence that is not walkable.

Examples

Input 1

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

Output 1

4

Input 2

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

Output 2

infinity

Subtasks

Subtask 1 (7 points)

No additional constraints.