sakura

Tassadar, primarul orașului Araoșimit, a plantat pe bulevarde cireși japonezi. Cu trecerea timpului, aceștia au crescut mari și frumoși, numai că... acum sunt prea mari și ramurile lor îngreunează traficul. Din acest motiv, primarul a hotărât că ar fi cazul să taie câteva ramuri, dar să păstreze frumusețea copacilor.

Cerinţă

Se dau $T$ perechi de arbori $(A, B)$ cu rădăcini fixate și se cere să spuneți numărul minim de operații care trebuie efectuate asupra arborelui $A$ astfel încât acesta să devină izomorf cu arborele $B$, sau să menționați dacă acest lucru nu este posibil. O operație constă în ștergerea unei frunze din arborele $A$.

Date de intrare

Fişierul de intrare sakura.in conţine pe prima linie un singur număr natural $T$, reprezentând numărul de perechi de arbori. În continuare vor fi descrise cele $T$ perechi. Pe prima linie din descrierea fiecărei perechi se află numărul $N$, reprezentând numărul de noduri din primul arbore (asupra căruia se vor efectua operațiile). Pe următoarele $N - 1$ linii se vor afla câte două numere $x$ și $y$, cu semnificația că există muchie între nodurile cu indicii $x$ și $y$. Pe următoarea linie se află un număr $M$, reprezentând numărul de noduri din al doilea arbore. Pe următoarele $M - 1$ linii se vor afla câte două numere $x$ și $y$, cu semnificația că există muchie între nodurile cu indicii $x$ și $y$.

Date de ieșire

În fişierul de ieşire sakura.out se vor afișa $T$ linii. Pe fiecare linie veți scrie câte un singur număr natural, reprezentând răspunsul pentru fiecare pereche de arbori, în ordinea dată în fișierul de intrare. Dacă, pentru o pereche, este posibil să se obțină al doilea arbore din primul, veți afișa numărul minim de operații. Altfel, veți afișa -1.

Restricții și precizări

• $1 \leq T \leq 10$;
• $1 \leq N, M \leq 500$;
• Pentru $20$ din teste $N, M \leq 13$;
• Pentru $60$ din teste $N, M \leq 100$;
• Nodurile arborilor sunt numerotate de la $0$;
• Toți arborii au ca rădăcină nodul cu indicele $0$;
• După eliminarea unei frunze, este posibil ca tatăl frunzei respective să devină și el frunză și să poată fi șters;
• Doi arbori se consideră izomorfi dacă au aceeași rădăcină și există o posibilitate de reetichetare a nodurilor primului arbore astfel încât cei doi arbori să fie identici.

Exemplu

sakura.in

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

sakura.out

2
-1

Explicație

Pentru prima pereche, putem șterge, în această ordine, nodurile $3$ și $1$. Cei doi arbori rămași sunt izomorfi, deoarece au aceeași rădăcină $(0)$, și putem reeticheta nodul $2$ din primul arbore cu $1$. Astfel, vor deveni identici. Pentru a doua pereche, nu există soluție.