CSES - Nakkikioskit
  • Time limit: 4.00 s
  • Memory limit: 128 MB

Uolevi matkustelee usein kaupungista toiseen ja valitsee aina lyhimmän reitin kahden kaupungin välillä. Matkansa aikana hän syö nakkisämpylän jokaisessa kaupungissa, jossa on nakkikioski.

Tehtäväsi on laskea, montako nakkisämpylää Uolevi syö yhteensä kullakin matkalla. Uolevi syö nakkisämpylän myös matkan ensimmäisessä ja viimeisessä kaupungissa, jos niissä on nakkikioski.

Kaupunkiverkosto on muodostunut siten, että minkä tahansa kahden kaupungin välillä on reitti, mutta tiet eivät muodosta yhtään sykliä.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: kaupunkien määrä. Kaupungit on numeroitu kokonaisluvuin 1,2,\ldots,n.

Sitten syötteessä on n-1 riviä, joista jokainen kuvaa yhden tien. Kullakin rivillä on kaksi kokonaislukua: mistä kaupungista mihin kaupunkiin tie johtaa. Kaikki tiet ovat kaksisuuntaisia.

Tämän jälkeen syötteessä on kokonaisluku k: monessako kaupungissa on nakkikioski. Tämän jälkeen omalla rivillään on k kokonaislukua, jotka kertovat, missä kaupungeissa on nakkikioski.

Lopuksi syötteessä on kokonaisluku q: kyselyiden määrä. Tämän jälkeen on q riviä, joista jokainen kuvaa yhden kyselyn. Kullakin rivillä on kaksi kokonaislukua a ja b: mistä kaupungista mihin kaupunkiin Uolevi matkustaa.

Tuloste

Ohjelmasi tulee tulostaa jokaista kyselyä kohden yksi kokonaisluku: montako nakkisämpylää Uolevi syö matkan aikana.

Rajat

  • 1 \le n \le 5\cdot 10^4
  • 1 \le k \le n
  • 1 \le q \le 10^5
  • 1 \le a, b \le n

Esimerkki

Syöte:

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

Tuloste:

1
2
0