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