Дано дерево на n вершинах (связный неориентированный ациклический граф c n−1 рёбрами), где у каждого ребра есть вес w. Назовём простой путь длины k возрастающим , если существует такое целое x>=2, что вес первого ребра пути делится на x, второго ребра — делится на x2, ……, вес k-го ребра делится на xk.
Требуется найти максимальную длину k возрастающего пути, где k — количество рёбер в нём.
Входные данные
В первой строке вводится единственное целое число n (1 <= n <= 100000) - число вершин в дереве.
В следующих n−1 строках вводятся по три целых числа u, v, w ( 1<= v <= n, 1<= w <= n, u ≠ v, 1 <= w <= 107) - номера вершин, которые соединяет очередное ребро, и его вес.
Выходные данные
Выведите одно целое число k - максимальную длину возрастающего пути.
Примечание
Простым путем называется такой путь, что все вершины в нем различны.
В 1-м примере есть путь длины 2: 3 — 1 — 2. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.
Во 2-м примере есть путь длины 3: 3 — 4 — 5 — 6. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 2 8
1 3 6
1 4 3
|
2
|
| 2 |
6
1 2 2
2 3 4
3 4 2
4 5 4
5 6 8
|
3
|