Se le da un árbol formado por ~n~ nodos. Su tarea consiste en determinar para cada nodo la suma de las distancias del nodo a todos los demás nodos.

Entrada

La primera línea de entrada contiene un número entero ~n~: el número de nodos. Los nodos se numeran ~1,2,\ldots,n.~ Luego hay ~n-1~ líneas que describen las aristas. Cada línea contiene dos enteros ~a~ y ~b~: hay una arista entre los nodos ~a~ y ~b~.

Salida

Imprime ~n~ enteros: para cada nodo ~1,2,\ldots,n~, la suma de las distancias.

Restricciones

• ~1 \le n \le 2 \cdot 10^5~
• ~1 \le a,b \le n~

Ejemplo de entrada

5
1 2
1 3
3 4
3 5

Ejemplo de Salida

6 9 5 8 8