Syrjälässä on n juna-asemaa, jotka ovat yhteydessä n-1:llä kilometrin pituisilla ratapätkillä.

Rautateitä ylläpitävä yhtiö Syrjälän Rautaa-tiet on uhannut sulkea kaikki asemat matkustajien musiikkimaun vuoksi.

Syrjälän kaupunginvaltuustolla on q suunnitelmaa, joissa innessä m_ille asemalle annettaisiin kaiuttimet, jotka soittavat kovalla hevimusiikkia.

Syrjälän Rautaa-teiden johtajien mielestä asema on välttämätön, jos kyseisellä asemalla soitetaan hevimusiikkia, tai jos sieltä lähtee vähintään kolmeen suuntaan ratoja heviä soittavia asemia kohti.

Mitkä asemat pidetään auki ja mitä yhteyksiä olisi tarjolla, jos kaikki paitsi välttämättömät asemat suljetaan?

"Yhteys" on pari auki olevia asemia, joiden välillä ei ole auki olevia asemia. Yhteyden pituus on etäisyys asemien välillä ratapätkiä pitkin kilometreissä.

Syöte

Ensimmäisellä rivillä on luku n: asemien määrä syrjälässä.

Seuraavalla n-1:llä rivillä on jokaisella kaksi lukua a ja b, jotka kertovat asemien a ja b välillä olevan ratapätkä.

Voit olettaa, että kaikilta asemilta pääsee kaikille asemille ratapätkiä pitkin.

Seuraavalla rivillä on yksi luku q: suunnitelmien määrä.

Seuraavalla q parilla rivejä on jokaisella ensimmäisellä yksi luku m_i, asemien joille kaiuttimet asennetaan lukumäärä suunnitelmassa, ja toisella rivillä nämä m_i asemaa.

Tuloste

Jokaisen suunnitelman kohdalla, tulosta kuinka monta asemaa jäisi auki ja mitä yhteyksiä olisi tarjolla. Voit tulostaa yhteydet haluamassasi järjestyksessä.

Rajat

• 1 \leq n, q \leq 10^{5}
• 1 \leq \sum_{i} m_i \leq 2 \cdot 10^{5}

Esimerkki

Syöte:

10
1 2
1 3
3 4
2 5
3 6
5 7
5 8
6 9
6 10
3
4
3 7 8 10 
5
3 4 5 8 10 
3
4 9 10 

Tuloste:

5
3 10 2
3 5 3
7 5 1
8 5 1
5
3 10 2
3 4 1
3 5 3
5 8 1
4
4 6 2
9 6 1
10 6 1