Code Submission Evaluation System Login

Datatähti-valmennus

Junalinjat


Task | Statistics


CSES - Junalinjat

Time limit:1.00 s Memory limit:128 MB

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
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