Вам дано дерево из $$$n$$$ вершин. Определим значение пары $$$(u,v)$$$ ($$$1\leq u\leq v\leq n$$$) как размер наибольшей компоненты связности после удаления всех рёбер на пути от $$$u$$$ до $$$v$$$ в исходном дереве.
Для каждого $$$1\leq i\leq n$$$ требуется найти количество пар $$$(u,v)$$$, для которых их значение равно $$$i$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\leq n \leq 10^5$$$) — количество вершин.
Далее следуют $$$n-1$$$ строк, в $$$i$$$-й из них содержатся два целых числа $$$u$$$ и $$$v$$$ ($$$1\leq u,v\leq n$$$) — две вершины, которые соединяет $$$i$$$-е ребро.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5\cdot 10^5$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел, где $$$i$$$-е из них обозначает количество различных пар $$$(u,v)$$$, для которых их значение равно $$$i$$$.
7121 231 21 341 22 33 451 22 32 42 573 41 52 32 65 27 382 13 24 15 36 27 68 1
11 21 2 31 3 2 40 0 6 4 50 4 5 5 3 4 70 0 12 4 3 5 4 8
В первом наборе входных данных значение пары $$$(1, 1)$$$ равно $$$1$$$.
Во втором наборе входных данных значения пар $$$(1, 1)$$$ и $$$(2, 2)$$$ оба равны $$$2$$$, потому что никакие рёбра не будут удалены. Значение пары $$$(1, 2)$$$ равно $$$1$$$, потому что ребро $$$(1, 2)$$$ лежит на пути от $$$1$$$ до $$$2$$$ в дереве, и после его удаления останутся $$$2$$$ компоненты связности: $$$\{1\}$$$ и $$$\{2\}$$$, а размер наибольшей компоненты равен $$$1$$$.
В шестом наборе входных данных значение пары $$$(4, 6)$$$ равно $$$3$$$, потому что рёбра $$$(3, 4)$$$, $$$(2, 3)$$$ и $$$(2, 6)$$$ лежат на пути от $$$4$$$ до $$$6$$$, и после их удаления останутся $$$4$$$ компоненты связности: $$$\{1, 2, 5\}$$$, $$$\{3, 7\}$$$, $$$\{4\}$$$ и $$$\{6\}$$$, а размер наибольшей компоненты равен $$$3$$$.
