F. Удаление мостов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано корневое дерево, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Вершина $$$1$$$ является корнем. Кроме того, у корня есть только один ребенок.

Требуется добавить ровно $$$k$$$ рёбер в дерево (возможно, кратные рёбра и/или рёбра, уже существующие в дереве).

Напомним, что мост — это такое ребро, что после его удаления количество компонент связности в графе увеличивается. Таким образом, изначально все рёбра дерева являются мостами.

После добавления $$$k$$$ рёбер некоторые изначальные рёбра дерева остаются мостами, а некоторые перестают ими быть. Необходимо удовлетворить два условия:

  • для каждого моста все рёбра дерева в поддереве нижней вершины этого моста также должны быть мостами;
  • количество мостов должно быть как можно меньше.

Решите задачу для всех значений $$$k$$$ от $$$1$$$ до $$$n - 1$$$ и выведите наименьшее количество мостов.

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

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

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — количество вершин дерева.

В каждой из следующих $$$n - 1$$$ строк записаны два целых числа $$$v$$$ и $$$u$$$ ($$$1 \le v, u \le n$$$) — описание рёбер дерева. Гарантируется, что заданные рёбра образуют валидное дерево.

Дополнительное ограничение на входные данные: корень (вершина $$$1$$$) имеет ровно одного ребенка.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.

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

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

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