GCD Counting
Description
You are given a tree consisting of $n$ vertices. A number is written on each vertex; the number on vertex $i$ is equal to $a_i$.
Let's denote the function $g(x, y)$ as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex $x$ to vertex $y$ (including these two vertices). Also let's denote $dist(x, y)$ as the number of vertices on the simple path between vertices $x$ and $y$, including the endpoints. $dist(x, x) = 1$ for every vertex $x$.
Your task is calculate the maximum value of $dist(x, y)$ among such pairs of vertices that $g(x, y) > 1$.
The first line contains one integer $n$ — the number of vertices $(1 \le n \le 2 \cdot 10^5)$.
The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ $(1 \le a_i \le 2 \cdot 10^5)$ — the numbers written on vertices.
Then $n - 1$ lines follow, each containing two integers $x$ and $y$ $(1 \le x, y \le n, x \ne y)$ denoting an edge connecting vertex $x$ with vertex $y$. It is guaranteed that these edges form a tree.
If there is no pair of vertices $x, y$ such that $g(x, y) > 1$, print $0$. Otherwise print the maximum value of $dist(x, y)$ among such pairs.
Input
The first line contains one integer $n$ — the number of vertices $(1 \le n \le 2 \cdot 10^5)$.
The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ $(1 \le a_i \le 2 \cdot 10^5)$ — the numbers written on vertices.
Then $n - 1$ lines follow, each containing two integers $x$ and $y$ $(1 \le x, y \le n, x \ne y)$ denoting an edge connecting vertex $x$ with vertex $y$. It is guaranteed that these edges form a tree.
Output
If there is no pair of vertices $x, y$ such that $g(x, y) > 1$, print $0$. Otherwise print the maximum value of $dist(x, y)$ among such pairs.
Samples
3
2 3 4
1 2
2 3
1
3
2 3 4
1 3
2 3
2
3
1 1 1
1 2
2 3
0