У Монокарпа есть дерево, состоящее из \(n\) вершин.
Он планирует выбрать некоторую вершину \(r\) и проделать следующие операции над каждой вершиной \(v\) от \(1\) до \(n\):
Раскраска называется красивой, если она удовлетворяет двум условиям:
Обратите внимание, что Монокарп может выбирать любое количество различных цветов, которые он хочет использовать.
Для каждого использованного цвета он затем считает количество вершин этого цвета. Стоимость дерева — это минимум из этих значений.
Какая может быть наибольшая стоимость дерева?
В первой строке записано одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.
В первой строке записано одно целое число \(n\) (\(3 \le n \le 2 \cdot 10^5\)) — количество вершин в дереве.
В каждой из следующих \(n-1\) строк записаны два целых числа \(v\) и \(u\) (\(1 \le v, u \le n\)) — описание ребра.
Заданные ребра образуют дерево. Сумма \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).
На каждый набор входных данных выведите одно целое число — наибольшая возможная стоимость дерева.
4 4 1 2 2 3 3 4 5 1 2 1 3 1 4 1 5 3 1 3 3 2 7 3 2 2 5 7 5 3 1 1 6 1 4
4 1 3 3
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач