Instant Noodles
Contest: Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 2300
Tags: graphs, hashing, math, number theory

Wu got hungry after an intense training session, and came to a nearby store to buy his favourite instant noodles. After Wu paid for his purchase, the cashier gave him an interesting task.

You are given a bipartite graph with positive integers in all vertices of the right half. For a subset $$$S$$$ of vertices of the left half we define $$$N(S)$$$ as the set of all vertices of the right half adjacent to at least one vertex in $$$S$$$, and $$$f(S)$$$ as the sum of all numbers in vertices of $$$N(S)$$$. Find the greatest common divisor of $$$f(S)$$$ for all possible non-empty subsets $$$S$$$ (assume that GCD of empty set is $$$0$$$).

Wu is too tired after his training to solve this problem. Help him!

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 500\,000$$$) — the number of test cases in the given test set. Test case descriptions follow.

The first line of each case description contains two integers $$$n$$$ and $$$m$$$ ($$$1~\leq~n,~m~\leq~500\,000$$$) — the number of vertices in either half of the graph, and the number of edges respectively.

The second line contains $$$n$$$ integers $$$c_i$$$ ($$$1 \leq c_i \leq 10^{12}$$$). The $$$i$$$-th number describes the integer in the vertex $$$i$$$ of the right half of the graph.

Each of the following $$$m$$$ lines contains a pair of integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), describing an edge between the vertex $$$u_i$$$ of the left half and the vertex $$$v_i$$$ of the right half. It is guaranteed that the graph does not contain multiple edges.

Test case descriptions are separated with empty lines. The total value of $$$n$$$ across all test cases does not exceed $$$500\,000$$$, and the total value of $$$m$$$ across all test cases does not exceed $$$500\,000$$$ as well.

Output format:
For each test case print a single integer — the required greatest common divisor.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
The greatest common divisor of a set of integers is the largest integer $$$g$$$ such that all elements of the set are divisible by $$$g$$$.

In the first sample case vertices of the left half and vertices of the right half are pairwise connected, and $$$f(S)$$$ for any non-empty subset is $$$2$$$, thus the greatest common divisor of these values if also equal to $$$2$$$.

In the second sample case the subset $$$\{1\}$$$ in the left half is connected to vertices $$$\{1, 2\}$$$ of the right half, with the sum of numbers equal to $$$2$$$, and the subset $$$\{1, 2\}$$$ in the left half is connected to vertices $$$\{1, 2, 3\}$$$ of the right half, with the sum of numbers equal to $$$3$$$. Thus, $$$f(\{1\}) = 2$$$, $$$f(\{1, 2\}) = 3$$$, which means that the greatest common divisor of all values of $$$f(S)$$$ is $$$1$$$.

Example input:
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

Example output:
2
1
12

Editorial:
Let's split vertices of right half of graph in groups in such a way that group consists of vertices with same neighboring set. Then answer equals to $$$gcd$$$ of sums of numbers in all groups except the group with empty neighboring set. Let's prove it.
If there are some vertices with same list of neighbors then they will both in some $$$N(S)$$$ or none of them will be in it. It means that we can replace such vertices with one vertex with value equals to sum of values in these vertices. After that numbers in all vertices are divisible by answer and thus sum of every subset is divisible by it. Let's divide all the numbers by answer and prove that after it answer will be 1.
Consider some integer $$$k$$$ and we'll find some set of vertices $$$S$$$ such that $$$f(S)$$$ is not divisible by $$$k$$$. If sum of all numbers is not divisible by $$$k$$$ we can take all the left half and its sum is not divisible by $$$k$$$. Otherwise consider a vertex with minimum degree such that its value is not divisible by $$$k$$$ (such vertex exists because gcd of numbers in right half is 1 now). Let's take subset of vertices in left part which are not connected to $$$v$$$. Which vertices are not neighboring to this set? It is $$$v$$$ and all the vertices that their neighboring set it a subset of neighboring set of $$$v$$$ (and their sum is divisible by $$$k$$$). But value of $$$v$$$ is not divisible by $$$k$$$ so sum in complement of its neighboring set is not divisible by $$$k$$$ too.