Se le proporciona un árbol compuesto por ~n~ nodos y ~m~ rutas.

Su tarea consiste en calcular, para cada nodo, el número de rutas que lo contienen.

Entrada

• La primera línea de entrada contiene los enteros ~n~ y ~m~: el número de nodos y rutas. 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~: existe una arista entre los nodos ~a~ y ~b~.
• Finalmente, hay ~m~ líneas que describen las rutas. Cada línea contiene dos enteros ~a~ y ~b~: existe una ruta entre los nodos ~a~ y ~b~.

Salida

Imprima ~n~ enteros: para cada nodo ~1,2,\ldots,n~, el número de rutas que contienen ese nodo.

Restricciones

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

Ejemplo de Entrada

5 3
1 2
1 3
3 4
3 5
1 3
2 5
1 4

Ejemplo de Salida

3 1 3 1 1