Even distribution

Time limit3sMemory limit256 MB

Summary

Count how many integers occur as the greatest common divisor of candy counts along some walk in the island graph.

Level: Medium7 of 10
Topics: Number theory, Graph, DFS
Solved: No attempts yet

Problem

Endre has many nieces and nephews. Once a year he takes some of them on a trip to an archipelago, where a boat company runs two way services between some pairs of islands. Endre and the children can fly directly in and out of any island, so a trip is a nonempty sequence of islands $i_1, i_2, \dots, i_n$ in which consecutive islands $i_j$ and $i_{j+1}$ are joined by a boat service. The first and the last island may be the same or different, and an island may be visited more than once.

Every island makes its own kind of candy and gives each arriving group a fixed number of pieces. Endre does not eat candy, but the children finish theirs at once. To keep the peace, every time the group lands on an island and receives candy he splits it evenly among the children. If he brings $k$ children, the candy count of every island the trip visits must be divisible by $k$ .

The travel agency sends him the trip plan, the sequence $i_1, i_2, \dots, i_n$ , in advance. He wants to bring as many of the children as possible, so he works out the largest number $k$ of children he can bring without breaking the even split rule. He brings at least one child. Each trip plan fixes exactly one number of children.

Over the years the number of children has been different every time. Endre wants to know how many group sizes are possible. Count the integers $k$ such that some trip plan makes him bring exactly $k$ children.

Input

The first line contains two integers $I$ and $S$ ( $1 \le I, S \le 10^4$ ), the number of islands and the number of boat services. Islands are numbered with distinct integers from $1$ to $I$ .

The second line contains $I$ integers $C_1, C_2, \dots, C_I$ , where $C_i$ is the number of pieces of candy the group receives on island $i$ ( $1 \le C_i \le 10^5$ ).

Each of the next $S$ lines contains two integers $A$ and $B$ ( $1 \le A < B \le I$ ) describing one boat service, which runs from island $A$ to island $B$ and from island $B$ to island $A$ . No pair of islands is joined by more than one service.

Output

Print one line with the number of integers $k$ such that some trip plan makes Endre bring exactly $k$ children.

Examples3

Example 1
Input
```
2 1
1 9
1 2
```
Expected output
```
2
```
Example 2
Input
```
4 2
1 2 3 4
1 3
1 2
```
Expected output
```
4
```
Example 3
Input
```
4 3
30 42 105 70
2 4
1 2
2 3
```
Expected output
```
11
```