给你一棵由 $$$n$$$ 个顶点组成的树。每个顶点上都写有一个数字;顶点 $$$i$$$ 上的数字等于 $$$a_i$$$。
让我们将函数 $$$g(x, y)$$$ 表示为属于从顶点 $$$x$$$ 到顶点 $$$y$$$(包括这两个顶点)的简单路径的顶点上所写的数字的最大公约数。另外,我们将 $$$dist(x, y)$$$ 表示为顶点 $$$x$$$ 和 $$$y$$$ 之间的简单路径上的顶点数,包括端点。对于每个顶点 $$$x$$$,$$$dist(x, x) = 1$$$。
你的任务是计算 $$$g(x, y) > 1$$$ 的顶点对中 $$$dist(x, y)$$$ 的最大值。
输入
第一行包含一个整数 $$$n$$$ — 顶点数 $$$(1 \le n \le 2 \cdot 10^5)$$$。
第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ $$$(1 \le a_i \le 2 \cdot 10^5)$$$ — 写在顶点上的数字。
接下来是 $$$n - 1$$$ 行,每行包含两个整数 $$$x$$$ 和 $$$y$$$ $$$(1 \le x, y \le n, x \ne y)$$$ 表示连接顶点 $$$x$$$ 与顶点 $$$y$$$ 的边。保证这些边形成一棵树。
输出
如果没有一对顶点 $$$x, y$$$ 使得 $$$g(x, y) > 1$$$,则打印 $$$0$$$。否则打印这些对中 $$$dist(x, y)$$$ 的最大值。
示例
输入 #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