- Prepare
- Algorithms
- Graph Theory
- Coprime Paths

# Coprime Paths

# Coprime Paths

You are given an undirected, connected graph, , with nodes and edges where . Each node is initially assigned a value, , that has *at most* prime divisors.

You must answer queries in the form `u v`

. For each query, find and print the *number of pairs* of nodes on the path between and such that and the length of the path between and is minimal among all paths from to .

**Input Format**

The first line contains two space-separated integers describing the respective values of and .

The second line contains space-separated integers describing the respective values of .

Each of the subsequent lines contains two space-separated integers, and , describing an edge between nodes and .

Each of the subsequent lines contains two space-separated integers, and , describing a query.

**Constraints**

**Output Format**

For each query, print an integer on a new line denoting the *number of pairs* of nodes on the path between and such that and the length of the path between and is minimal among all paths from to .

**Sample Input 0**

```
6 5
3 2 4 1 6 5
1 2
1 3
2 4
2 5
3 6
4 6
5 6
1 1
1 6
6 1
```

**Sample Output 0**

```
9
6
0
3
3
```

**Explanation 0**

The diagram below depicts graph and the paths specified by each query, as well as the *Pair Values* for each path in the form :

Recall that, for each queried path, we want to find and print the number of pairs of nodes such that .