Отборочный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"F" Два поддерева
Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт

Рассмотрим подвешенное дерево. Рассмотрим вершину v, имеющую в поддереве хотя бы одну вершину на расстоянии k от v. Будем называть k-поддеревом вершины v дерево, полученное из поддерева вершины v удалением всех вершин, расстояние от которых до v больше k. Например, на иллюстрации ниже красным отмечено 2-поддерево вершины 3.

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

Дано подвешенное дерево. Требуется определить наибольшее k такое, что у него есть два одинаковых k-поддерева, корни которых различны. Эти поддеревья могут пересекаться.

На рисунке приведены деревья из примеров.

В первом примере корни одинаковых 1-поддеревьев — это вершины 2 и 3.

Во втором примере корни одинаковых 3-поддеревьев — это вершины 1 и 4.

В третьем примере корни одинаковых 0-поддеревьев — это вершины 1 и 2.

Формат входных данных

В первой строке задано число t — количество тестов (1 ≤ t ≤ 104).

Каждый из t тестов описывается следующим образом: в первой строке задано число n — количество вершин (2 ≤ n ≤ 105).

Далее следует n строк. В i-й из них задано число cnti — количество детей вершины i, а далее следуют cnti чисел — номера детей вершины i. Вершины нумеруются с единицы. Корнем дерева является вершина 1. Гарантируется, что заданный граф является деревом с корнем в 1.

Сумма n по всем тестам в одних входных данных не превосходит 2·105.

Формат выходных данных

Для каждого теста выведите на отдельной строке максимальное k такое, что существует два одинаковых k-поддерева с разными корнями.

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

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.