Відстань на дереві II

Дано дерево, що складається з $n$ вершин.

Для кожної вершини знайдіть суму відстаней від неї до всіх інших вершин.

Вхідні дані

У першому рядку задано ціле число $n(1\le n\le 2\cdot 10^5)$ — кількість вершин. Вершини пронумеровані від $1$ до $n$.

Наступні $n-1$ рядків описують ребра дерева. Кожен рядок містить два числа $a$ та $b(1\le a,b\le n)$, що позначають вершини, з'єднані ребром.

Вихідні дані

Виведіть $n$ цілих чисел. Для кожної вершини від $1$ до $n$ виведіть суму відстаней від неї до всіх інших вершин.

Приклади