Description

给定一个无向图，包含 $n$ 个顶点和 $m$ 条边。每个顶点 $v$ 上写有一个数字 $a_v$，该数字为 $0$ 或 $1$。

一次“行走”是指在图中经过一系列顶点 $v_1v_2\dots v_k$，使得任意相邻的两个顶点之间都有一条边相连。

我们称一个二进制序列

是“可行走的”，如果存在一次行走 $v_1v_2\dots v_k$，满足 $a_{v_1}a_{v_2}\dots a_{v_k} = s$。

换句话说，如果可以通过在图中行走，并按经过顶点的顺序记录下顶点上的二进制数字，得到序列 $s$，则称 $s$ 是可行走的。

如图 B.1 所示为样例输入 1 的可视化示例。长度不超过 3 的所有二进制序列都是可行走的。

:::align{center}

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

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

Input Format

输入包含以下内容：

• 第一行包含两个整数 $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 \in \{0, 1\}$），表示每个顶点上写的数字。
• 接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，$u \neq v$），表示顶点 $u$ 和 $v$ 之间有一条边。保证任意一对顶点之间至多只有一条边。

Output Format

如果所有的二进制序列都是可行走的，输出 $\texttt{infinity}$。

否则，输出最短的不可行走的二进制序列的长度。

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

Hint

由 ChatGPT 4.1 翻译