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

Jokaisen kyselyn alussa on kokonaisluku t: kyselyn tyyppi. Jos tyyppi on 1, tehtävänä on laskea nakkikioskit Uolevin reitillä. Tällöin rivillä on vielä kokonaisluvut a ja b: 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 x: kaupunki, jossa tuhopolttaja iskee.

Tuloste

Ohjelmasi tulee tulostaa jokaista tyypin 1 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
5
1 1 4
1 1 3
1 2 4
2 3
1 1 3

Tuloste:

1
2
0
1