给定一个包含 $n$ 个顶点和 $m$ 条边的无向图。每个顶点 $v$ 上都写有一个数字 $a_v$，该数字为 $0$ 或 $1$。游走（walk）是指图中一个顶点序列 $v_1v_2 \dots v_k$，其中任意两个相邻顶点之间都有一条边相连。我们称一个二进制序列 $s = s_1s_2 \dots s_k$ 是可游走的（walkable），如果图中存在一个游走 $v_1v_2 \dots v_k$ 满足 $a_{v_1}a_{v_2} \dots a_{v_k} = s$。

换句话说，如果可以通过在图中游走并按访问顺序记录下顶点上的二进制数字来得到序列 $s$，则称该二进制序列是可游走的。图 B.1 展示了一个示例。

图 B.1：样例输入 1 的示意图。所有长度不超过 3 的二进制序列都是可游走的。

你的任务是找到最短的不可游走二进制序列的长度。

输入格式

输入包含： 一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 3 \cdot 10^5$, $0 \le m \le 3 \cdot 10^5$)，分别表示顶点数和边数。 一行包含 $n$ 个整数 $a_1, \dots, a_n$ ($a_v \in \{0, 1\}$，对于每个 $v$)，其中 $a_v$ 是写在顶点 $v$ 上的数字。 * $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示顶点 $u$ 和 $v$ 之间有一条边相连。保证每对顶点之间最多只有一条边。

输出格式

如果所有二进制序列都是可游走的，输出 “infinity”。否则，输出最短的不可游走二进制序列的长度。

样例

样例输入 1

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

样例输出 1

4

样例输入 2

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

样例输出 2

infinity

样例输入 3

1 0
0

样例输出 3

1