CSES - Nakkikioskit
  • Time limit: 0.50 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 matkalla olevassa kaupungissa, jossa on nakkikioski. Uolevi syö nakkisämpylän myös matkan ensimmäisessä ja viimeisessä kaupungissa, jos niissä on nakkikioski.

Toisinaan nakkikioskien määrä vähenee, koska ne ovat tuhopolttajan suosiossa. Tehtäväsi on laskea montako nakkisämpylää Uolevi syö kullakin matkallaan ottaen huomioon tuhopolttajan työn.

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 nn: kaupunkien määrä. Kaupungit on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Sitten syötteessä on n1n-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 kk: monessako kaupungissa on nakkikioski. Tämän jälkeen omalla rivillään on kk kokonaislukua, jotka kertovat, missä kaupungeissa on nakkikioski.

Lopuksi syötteessä on kokonaisluku qq: kyselyiden määrä. Tämän jälkeen on qq riviä, joista jokainen kuvaa yhden kyselyn.

Jokaisen kyselyn alussa on kokonaisluku tt: kyselyn tyyppi. Jos tyyppi on 1, tehtävänä on laskea nakkikioskit Uolevin reitillä. Tällöin rivillä on vielä kokonaisluvut aa ja bb: mistä kaupungista Uolevi lähtee ja mihin hän päätyy. Jos tyyppi on 2, tuhopolttaja hävittää nakkikioskin. Tällöin rivillä on vielä kokonaisluku xx: kaupunki, jossa tuhopolttaja iskee.

Tuloste

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

Rajat

  • 1n51041 \le n \le 5\cdot 10^4
  • 1kn1 \le k \le n
  • 1q1051 \le q \le 10^5
  • 1a,bn1 \le a, b \le n

Esimerkki

Syöte:

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

Tuloste:

1
2
0
1