#P1101D. GCD Counting

    ID: 2903 远端评测题 4000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>data structuresdfs and similardpnumber theorytrees*2000

GCD Counting

Description

You are given a tree consisting of nn vertices. A number is written on each vertex; the number on vertex ii is equal to aia_i.

Let's denote the function g(x,y)g(x, y) as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex xx to vertex yy (including these two vertices). Also let's denote dist(x,y)dist(x, y) as the number of vertices on the simple path between vertices xx and yy, including the endpoints. dist(x,x)=1dist(x, x) = 1 for every vertex xx.

Your task is calculate the maximum value of dist(x,y)dist(x, y) among such pairs of vertices that g(x,y)>1g(x, y) > 1.

The first line contains one integer nn — the number of vertices (1n2105)(1 \le n \le 2 \cdot 10^5).

The second line contains nn integers a1a_1, a2a_2, ..., ana_n (1ai2105)(1 \le a_i \le 2 \cdot 10^5) — the numbers written on vertices.

Then n1n - 1 lines follow, each containing two integers xx and yy (1x,yn,xy)(1 \le x, y \le n, x \ne y) denoting an edge connecting vertex xx with vertex yy. It is guaranteed that these edges form a tree.

If there is no pair of vertices x,yx, y such that g(x,y)>1g(x, y) > 1, print 00. Otherwise print the maximum value of dist(x,y)dist(x, y) among such pairs.

Input

The first line contains one integer nn — the number of vertices (1n2105)(1 \le n \le 2 \cdot 10^5).

The second line contains nn integers a1a_1, a2a_2, ..., ana_n (1ai2105)(1 \le a_i \le 2 \cdot 10^5) — the numbers written on vertices.

Then n1n - 1 lines follow, each containing two integers xx and yy (1x,yn,xy)(1 \le x, y \le n, x \ne y) denoting an edge connecting vertex xx with vertex yy. It is guaranteed that these edges form a tree.

Output

If there is no pair of vertices x,yx, y such that g(x,y)>1g(x, y) > 1, print 00. Otherwise print the maximum value of dist(x,y)dist(x, y) among such pairs.

Samples

样例输入 1

3
2 3 4
1 2
2 3

样例输出 1

1

样例输入 2

3
2 3 4
1 3
2 3

样例输出 2

2

样例输入 3

3
1 1 1
1 2
2 3

样例输出 3

0