E. Радужная ветка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево с $$$n$$$ вершинами, необходимо назначить цвет каждому ребру. Определим неудобство назначения как максимальное количество цветов на пути между любыми двумя вершинами.

Необходимо назначить ровно $$$k$$$ различных цветов (каждый цвет должен появиться хотя бы один раз) для рёбер, минимизируя неудобство назначения.

Пожалуйста, вычислите минимальное неудобство для всех $$$k=1,2,\ldots,n-1$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка входных данных содержит одно положительное целое число $$$n$$$ ($$$3\le n\le3\cdot10^5$$$) — количество вершин.

Каждая из следующих $$$n-1$$$ строк содержит по два целых положительных числа $$$u_i,v_i$$$ ($$$1\le u_i,v_i\le n$$$) — указывая, что между вершинами $$$u_i$$$ и $$$v_i$$$ есть ребро.

Гарантируется, что рёбра во входных данных образуют дерево.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3\cdot10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую $$$n-1$$$ целое число. $$$i$$$-е число представляет минимальное неудобство для $$$k=i$$$.

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

В первом наборе входных данных возможные решения для $$$k=1,2,\ldots,n-1$$$ следующие: