CF1322C Instant Noodles

Wu 在一次激烈的训练后感到饥饿，来到附近的商店购买他最喜欢的方便面。在 Wu 付款后，收银员给了他一个有趣的任务。 给定一个二分图，右半部分的所有顶点上都标有正整数。对于左半部分顶点的一个子集 $S$，定义 $N(S)$ 为所有与 $S$ 中至少一个顶点相邻的右半部分顶点的集合，$f(S)$ 为 $N(S)$ 中所有顶点上的数之和。请你求出所有可能的非空子集 $S$ 的 $f(S)$ 的最大公约数（假设空集的最大公约数为 $0$）。 Wu 训练后太累了，无法解决这个问题。请你帮帮他！

第一行包含一个整数 $t$（$1 \leq t \leq 500\,000$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 500\,000$），分别表示二分图两部分的顶点数和边数。 第二行包含 $n$ 个整数 $c_i$（$1 \leq c_i \leq 10^{12}$），第 $i$ 个数表示右半部分第 $i$ 个顶点上的整数。 接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示左半部分第 $u_i$ 个顶点和右半部分第 $v_i$ 个顶点之间有一条边。保证图中没有重边。 各测试用例之间用空行分隔。所有测试用例中 $n$ 的总和不超过 $500\,000$，$m$ 的总和也不超过 $500\,000$。

对于每个测试用例，输出一个整数，表示所求的最大公约数。

一组整数的最大公约数是能整除该集合中所有元素的最大整数 $g$。 在第一个样例中，左半部分和右半部分的顶点两两相连，任意非空子集 $S$ 的 $f(S)$ 都为 $2$，因此这些值的最大公约数也是 $2$。 在第二个样例中，左半部分的子集 $\{1\}$ 与右半部分的顶点 $\{1, 2\}$ 相连，数之和为 $2$；子集 $\{1, 2\}$ 与右半部分的顶点 $\{1, 2, 3\}$ 相连，数之和为 $3$。因此 $f(\{1\}) = 2$，$f(\{1, 2\}) = 3$，这些值的最大公约数为 $1$。 由 ChatGPT 4.1 翻译