У Soroush и Keshi есть по одному пронумерованному корневому дереву на \(n\) вершин. У обоих деревьев корнем является вершина \(1\).
Раньше Soroush и Keshi воевали. После бесконечных десятилетий борьбы они, наконец, стали союзниками, чтобы подготовить раунд Codeforces. Чтобы отметить это счастливое событие, они решили сделать памятный граф на \(n\) вершинах.
Они добавляют ребро между вершинами \(u\) и \(v\) в памятный граф, если выполняются оба из следующих условий:
- Одна из вершин \(u\) и \(v\) является предком второй в дереве Soroush.
- Ни одна из вершин \(u\) и \(v\) не является предком другой в дереве Keshi.
Здесь вершина \(u\) считается предком вершины \(v\), если \(u\) лежит на пути от \(1\) (корня) к \(v\).
Выскочивший из ниоткуда Mashtali попытался найти максимальную клику в памятном графе. Он потерпел неудачу, потому что граф был слишком большим.
Помогите Mashtali, найдя размер максимальной клики в памятном графе.
Напомним, что клика — это такое подмножество вершин графа, каждые две из которых соединены ребром.
Выходные данные
Для каждого набора входных данных выведите одно целое число — размер максимальной клики в памятном графе.
Примечание
В первом и третьем наборах входных данных можно выбрать любую вершину.
Во втором наборе входных данных одна из максимальных клик — \(\{2, 3, 4, 5\}\).
В четвертом наборе входных данных одна из максимальных клик — \(\{3, 4, 6\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|