Bittimaan rataverkko muodostuu $n$ asemasta ja $n-1$ rataosuudesta niiden välillä. Miltä tahansa asemalta pääsee mille tahansa asemalle. Sinulle annetaan tiedot junalinjoista ja tehtäväsi on laskea, montako junaa kunkin aseman kautta kulkee.

Syöte

Syötteen alussa on kaksi kokonaislukua $n$ ja $m$: asemien määrä ja junalinjojen määrä. Asemat on numeroitu $1,2,\ldots,n$.

Sitten syötteessä on $n-1$ riviä, jotka kuvavat rataosuudet. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: asemien $a$ ja $b$ välissä on rataosuus. Kaikki rataosuudet ovat kaksisuuntaisia.

Lopuksi syötteessä on $m$ riviä, jotka kuvaavat junalinjat. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: junalinja kulkee asemien $a$ ja $b$ välillä. Jokaisen linjan pääteasemat ovat eri asemat.

Tuloste

Tulosta jokaisesta asemasta, montako junalinjaa sen kautta kulkee. Asema voi olla junalinjan pääteasema tai väliasema.

Rajat

• $1 \le n,m \le 10^5$
• $1 \le a,b \le n$

Esimerkki

Syöte:

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

Tuloste:

1 3 1 2 1