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

Вхідні дані

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

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

Вихідні дані

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

Приклади