Вам дан лес из $$$k$$$ корневых деревьев$$$^{\text{∗}}$$$. Дровосек Тимофей хочет вырубить весь лес, применяя такую операцию:
- Выбрать поддерево$$$^{\text{†}}$$$ какой-либо вершины одного из деревьев и удалить его из дерева.
Тимофей очень любит битовые операции, поэтому он хочет, чтобы побитовое ИЛИ размеров поддеревьев, которые он удалял, было максимальным. Помогите ему и найдите, какой максимальный результат он может получить.
$$$^{\text{∗}}$$$ Деревом называется связный граф без циклов, петель и кратных ребер. Лесом называется набор из одного или нескольких деревьев. В корневом дереве одна из вершин называется корнем.
$$$^{\text{†}}$$$ Поддерево вершины $$$v$$$ — это множество вершин, для которых $$$v$$$ лежит на кратчайшем пути от этой вершины до корня, включая вершину $$$v$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных содержит одно целое число $$$k$$$ ($$$1 \leq k \leq 10^6$$$) — количество деревьев в лесу.
Далее следует описание каждого из $$$k$$$ деревьев:
Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — размер дерева. Вершины дерева пронумерованы целыми числами от $$$1$$$ до $$$n$$$. Корнем дерева является вершина под номером $$$1$$$.
Вторая строка содержит $$$n - 1$$$ целое число $$$p_2, p_3, \ldots p_n$$$ ($$$1 \leq p_i < i$$$), где $$$p_i$$$ — предок вершины $$$i$$$.
Гарантируется, что сумма $$$k$$$ и $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите одно целое число — максимальный результат, который можно получить.
311241 2 261 1 3 1 31101 2 2 1 1 5 7 6 4
1 7 10
Во втором наборе входных данных деревья выглядят так:
Первой операцией удалим все второе дерево.
Второй операцией удалим вершину $$$4$$$ из первого дерева.
Третьей операцией удалим первое дерево. Результат равен $$$6|1|3 = 7$$$ ($$$|$$$ обозначает побитовое ИЛИ).
В третьем наборе входных данных нужно удалить все дерево.
