Un árbol no dirigido tiene \(n\) nodos, numerados de \(0\) a \(n - 1\). Para cada nodo \(u\), calcula la suma de sus distancias (en aristas) a todos los demás nodos.

Hacer un BFS desde cada nodo cuesta \(O(n^2)\): demasiado para \(n = 3 \cdot 10^4\).

Entrada

La primera línea tiene \(n\) \((1 \le n \le 3 \cdot 10^4)\). Cada una de las siguientes \(n - 1\) líneas tiene una arista \(a\) \(b\).

Salida

Las \(n\) sumas, en orden de nodo y separadas por espacios.

Ejemplo 1

Entrada

6
0 1
0 2
2 3
2 4
2 5

Salida

8 12 6 10 10 10

Ejemplo 2

Entrada

1

Salida

0

Ejemplo 3

Entrada

2
1 0

Salida

1 1