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