P13740 [NWERC 2024] Binary Search

给定一个无向图，包含 $n$ 个顶点和 $m$ 条边。每个顶点 $v$ 上写有一个数字 $a_v$，该数字为 $0$ 或 $1$。 一次“行走”是指在图中经过一系列顶点 $v_1v_2\dots v_k$，使得任意相邻的两个顶点之间都有一条边相连。 我们称一个二进制序列 $$s = s_1s_2\dots s_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 的所有二进制序列都是可行走的。 ::: 你的任务是找出最短的不可行走的二进制序列的长度。

输入包含以下内容： - 第一行包含两个整数 $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$ 之间有一条边。保证任意一对顶点之间至多只有一条边。

如果所有的二进制序列都是可行走的，输出 $\texttt{infinity}$。 否则，输出最短的不可行走的二进制序列的长度。

由 ChatGPT 4.1 翻译