Вам дано дерево из \(n\) вершин, в котором вершины пронумерованы от \(0\) до \(n-1\). Для каждого \(k\) от \(0\) до \(n\) включительно вам необходимо посчитать количество неупорядоченных пар \((u,v)\), \(u \neq v\), таких, что MEX всех номеров вершин на пути от \(u\) до \(v\) равен \(k\).
MEX последовательности целых чисел равен наименьшему неотрицательному целому числу, которое в ней не встречается.
Первая строка содержит целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит целое число \(n\) (\(2 \le n \le 2 \cdot 10^{5}\)).
Следующая \(n-1\) строка содержит описание дерева. Каждая строка содержит два целых числа \(u\) и \(v\) (\(0 \le u,v \le n-1\)), задающие ребро между \(u\) и \(v\) (\(u \neq v\)).
Гарантируется, что данные ребра образуют дерево.
Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^{5}\).
Для каждого набора входных данных выведите \(n+1\) целое число: число путей в дереве таких, что MEX всех номеров вершин на нем равен \(k\), для всех \(k\) от \(0\) до \(n\).
2 4 0 1 0 2 2 3 2 1 0
1 2 1 1 1 0 0 1
1500 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач