[AdditionalFile5407.zip](file://AdditionalFile5407.zip?type=additional_file)

#5407. 「OOI 2020 Day 2」方便面

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2020 Day2 T3 「Лапша быстрого приготовления / Instant Noodles」。

吴在激烈的训练后感到饥饿，于是前往最近的商店购买他最喜欢的方便面。在结账后，收银员给他提出了一个有趣的问题。

给定一个二分图，其中 右侧 部分的顶点上写有正整数。对于 左侧 部分顶点的子集 $S$，定义 $N(S)$ 为右侧部分中与 $S$ 中至少一个顶点相邻的顶点集合，$f(S)$ 为 $N(S)$ 中顶点上数字的和。要求找出所有可能的非空子集 $S$ 对应的 $f(S)$ 的最大公约数。

吴在训练中太过疲惫，无法解决这个问题。请帮助他！

输入格式

第一行包含一个整数 $t$ $(1 \leq t \leq 500000)$，表示需要解决的输入数据组数。接下来是输入数据的描述。

每组输入数据的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 500000)$，分别表示图中每个部分的顶点数量和边的数量。

第二行包含 $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$ 的总和不超过 $500000$，$m$ 的总和也不超过 $500000$。

输出格式

对于每组输入数据，输出一个数字，即所需的最大公约数。

样例

输入

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

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

4 7
36 31 96 29
1 2
1 3
1 4
2 2
2 4
3 1
4 3

输出

2
1
12

最大公约数是指一组数字中的最大整数 $g$，使得该组中的所有数字都能被 $g$ 整除。

在第一组输入数据中，左侧部分的所有顶点与右侧部分的所有顶点都通过边相连，因此对于任何非空子集，$f(S)$ 的值均为 $2$，所以最大公约数也为 $2$。

在第二组输入数据中，左侧部分的子集 $\{1\}$ 与右侧部分的顶点 $\{1, 2\}$ 相连，其值的和为 $2$；而左侧部分的子集 $\{1, 2\}$ 与右侧部分的顶点 $\{1, 2, 3\}$ 相连，其值的和为 $3$。因此，$f(\{1\}) = 2$，$f(\{1, 2\}) = 3$，这意味着所有 $f(S)$ 的最大公约数为 $1$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。