E. Весёлая жизнь в университете
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Егор и его друг Арсений в этом году заканчивают учиться в школе и уже скоро поступят университет. И так как они очень ответственные ребята, они начали готовиться к поступлению уже сейчас.

Прежде всего они решили позаботиться о том, где будут жить долгие четыре года обучения, и зайдя на сайт университета, выяснили, что общежитие университета можно представить в виде корневого дерева из $$$n$$$ вершин с корнем в вершине $$$1$$$. В дереве каждая вершина представляет собой рекреацию с некоторым видом активности $$$a_i$$$. Друзьям нужно выбрать $$$2$$$ рекреации (не обязательно различные), в которых они поселятся. Ребята убеждены, что тем будет веселее их жизнь, чем больше значение следующей функции $$$f(u, v) = diff(u, lca(u, v)) \cdot diff(v, lca(u, v))$$$. Помогите Егору и Арсению и найдите максимальное значение $$$f(u, v)$$$ среди всех пар рекреаций!

$$$^{\dagger} diff(u, v)$$$ — количество различных активностей, выписанных на простом пути от вершины $$$u$$$ до вершины $$$v$$$.

$$$^{\dagger} lca(u, v)$$$ — такая вершина $$$p$$$, что она находится на максимальном расстоянии от корня и является предком и вершины $$$u$$$, и вершины $$$v$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^{5}$$$).

Вторая строка каждого набора входных данных содержит $$${n - 1}$$$ целых чисел $$$p_2, p_3, \ldots,p_n$$$ ($$$1 \le p_i \le i - 1$$$), где $$$p_i$$$ — предок вершины $$$i$$$.

Третья строка каждого набора входных данных содержит $$${n}$$$ целых чисел $$$a_1, a_2, \ldots,a_n$$$ ($$$1 \le a_i \le n$$$), где $$$a_i$$$ — номер активности, которая находится в вершине $$$i$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите максимальное значение $$$f(u, v)$$$, по всем парам рекреаций $$$(u, v)$$$.

Пример
Входные данные
4
2
1
1 2
7
1 1 2 2 3 3
6 5 2 3 6 5 6
13
1 1 1 2 2 2 3 3 4 5 6 6
2 2 2 1 4 9 7 2 5 2 1 11 2
12
1 1 1 2 2 3 4 4 7 7 6
11 2 1 11 12 8 5 8 8 5 11 7
Выходные данные
2
9
9
12
Примечание

Рассмотрим четвертый набор входных данных. Дерево имеет такой вид:

Все рекреации раскрашены в цвета. Одинаковые цвета означает что активности в рекреациях совпадают. Рассмотрим пару вершин $$$(11, 12)$$$, $$$lca(11, 12) = 1$$$. Выпишем все активности на пути от $$$11$$$ до $$$1$$$ — $$$[11, 5, 1, 11]$$$, среди них различных активностей $$$3$$$, то есть $$$diff(11, 1) = 3$$$. Также выпишем все активности на пути от $$$12$$$ до $$$1$$$ — $$$[7, 8, 2, 11]$$$, среди них различных активностей $$$4$$$, то есть $$$diff(12, 1) = 4$$$. Получаем что $$$f(11, 12) = diff(12, 1) \cdot diff(11, 1) = 4 \cdot 3 = 12$$$, что и является ответом для данного дерева. Можно показать, что ответ лучше получить невозможно.