D. Подсчёт GCD
ограничение по времени на тест
4.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$n$$$ вершин. На каждой вершине дерева записано число; на $$$i$$$-й вершине записано число $$$a_i$$$.

Определим функцию $$$g(x, y)$$$ как наибольший общий делитель всех чисел, записанных на вершинах на простом пути от вершины $$$x$$$ до вершины $$$y$$$ (включая эти две вершины). Также определим $$$dist(x, y)$$$ как количество вершин на простом пути между $$$x$$$ и $$$y$$$, включая концы пути. $$$dist(x, x) = 1$$$ для каждой вершины $$$x$$$.

Посчитайте максимальное значение $$$dist(x, y)$$$ по всем таким парам вершин, что $$$g(x, y) > 1$$$.

Входные данные

В первой строке задано целое число $$$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)$$$ по всем таким парам.

Примеры
Входные данные
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