Laiko ribojimas: 2s

Atminties ribojimas: 256MB

Jei norite pateikti savo sprendimą - prisijunkite.

LCA

Jums duotas n viršūnių medis. Jums reikia atsakyti q užklausų - rasti žemiausią viršūnių v,w protėvį.

Pradiniai duomenys

Pirmoje eilutėje duotas testų skaičius t(1\\leqt\\leq20).

Pirmoje testo eilutėje duotas skaičius n(1\\leqn\\leq1000) - medžio viršūnių skaičius.

Sekančios n eilučių prasideda vienu skaičiumi m - i-tosios viršūnės vaikų skaičius. Toliau duota m skaičių - i - tosios viršūnės vaikų indeksai.

Kitoje eilutėje duotas vienas skaičius q(1\\leqq\\leq1000) - užklausų skaičius.

Kitose q eilučių duoti du skaičiai v,w - viršūnių indeksai, kurioms reikia surasti žemiausią bendrą protėvį.

Rezultatai

Kiekvieno testo rezultatai pradedami su "Testas i:"

Kiekvienai testo užklausai išveskite po vieną skaičių - užklausos atsakymą.

Pavyzdys

Duomenys Rezultatai 
1
7
1 2 
1 3 
2 4 5 
0 
2 6 7 
0 
0 
7
6 3
2 2
2 3
1 1
2 5
1 5
1 5
 
Testas 1:
3
2
2
1
2
1
1