CSES - Retket
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Bittimaassa on nn kaupunkia, joiden välillä on n1n-1 tietä. Minkä tahansa kahden kaupungin välillä on olemassa reitti.

Teet qq retkeä, joista jokainen lähtee jostakin kaupungista aa ja päätyy johonkin kaupunkiin bb suorinta reittiä.

Montako kertaa käyt kussakin kaupungissa retkiesi aikana?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja qq: kaupunkien määrä ja kyselyiden määrä. Kaupungit on numeroitu 1,2,,n1,2,\dots,n.

Sitten syötteessä on n1n-1 riviä, jotka kuvaavat tiet. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: kaupunkien aa ja bb välillä on tie.

Lopuksi syötteessä on qq riviä, jotka kuvaavat retket. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: matkaat kaupungista aa kaupunkiin bb.

Tuloste

Tulosta nn kokonaislukua: montako kertaa käyt kussakin kaupungissa retkiesi aikana.

Rajat

  • 1n,q21051 \le n,q \le 2 \cdot 10^5
  • 1a,bn1 \le a,b \le n

Esimerkki

Syöte:

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

Tuloste:

1 3 2 1 0