C. Деревья примирения
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Soroush и Keshi есть по одному пронумерованному корневому дереву на $$$n$$$ вершин. У обоих деревьев корнем является вершина $$$1$$$.

Раньше Soroush и Keshi воевали. После бесконечных десятилетий борьбы они, наконец, стали союзниками, чтобы подготовить раунд Codeforces. Чтобы отметить это счастливое событие, они решили сделать памятный граф на $$$n$$$ вершинах.

Они добавляют ребро между вершинами $$$u$$$ и $$$v$$$ в памятный граф, если выполняются оба из следующих условий:

  • Одна из вершин $$$u$$$ и $$$v$$$ является предком второй в дереве Soroush.
  • Ни одна из вершин $$$u$$$ и $$$v$$$ не является предком другой в дереве Keshi.

Здесь вершина $$$u$$$ считается предком вершины $$$v$$$, если $$$u$$$ лежит на пути от $$$1$$$ (корня) к $$$v$$$.

Выскочивший из ниоткуда Mashtali попытался найти максимальную клику в памятном графе. Он потерпел неудачу, потому что граф был слишком большим.

Помогите Mashtali, найдя размер максимальной клики в памятном графе.

Напомним, что клика — это такое подмножество вершин графа, каждые две из которых соединены ребром.

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

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

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

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

Третья строка каждого набора входных данных содержит $$$n-1$$$ целых чисел $$$b_2, \ldots, b_n$$$ $$$(1 \le b_i < i)$$$, $$$b_i$$$ — родитель вершины $$$i$$$ в дереве Keshi.

Гарантируется, что заданные графы являются деревьями.

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

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

Для каждого набора входных данных выведите одно целое число — размер максимальной клики в памятном графе.

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

В первом и третьем наборах входных данных можно выбрать любую вершину.

Во втором наборе входных данных одна из максимальных клик — $$$\{2, 3, 4, 5\}$$$.

В четвертом наборе входных данных одна из максимальных клик — $$$\{3, 4, 6\}$$$.