Вам дано дерево з \(N\) вершин. Для кожного \(len = 1, \ldots, N - 1\), порахуйте кількість простих шляхів у цьому дереві, довжина яких дорівнює \(len\).

Простим шляхом називається такий шлях, який проходить через кожну вершину не більше одного разу.

Формат вхідних даних

У першому рядку записано число \(N\) (\(1 \le N \le 100\,000\)), що означає кількість вершин у дереві.

Кожен із наступних \(N - 1\) рядків містить два цілих числа \(u\) і \(v\) (\(1 \le u, v \le N\)), що позначають, що вершини \(u\) і \(v\) з'єднані ребром між собою. Вершини пронумеровано від 1 до \(N\). Гарантується, що описаний граф є деревом.

Формат вихідних даних

Виведіть \(N - 1\) рядків. У \(i\)-му рядку запишіть кількість простих шляхів у даному дереві, довжина яких дорівнює \(i\).

Приклад вхідних даних

2
1 2

Приклад вихідних даних

1

Приклад вхідних даних

3
1 2
2 3

Приклад вихідних даних

2
1

Приклад вхідних даних

3
1 2
2 3

Приклад вихідних даних

3
3
0