У Монокарпа есть дерево, состоящее из $$$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$$$.
На каждый набор входных данных выведите одно целое число — наибольшая возможная стоимость дерева.
441 22 33 451 21 31 41 531 33 273 22 57 53 11 61 4
4 1 3 3
Название |
---|