== include(page="template/taskheader" task_id="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.
h2. Cerinta
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$.
Poveste şi cerinţă...
h2. 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$.
Fişierul de intrare $sakura.in$ ...
h2. 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"$.
În fişierul de ieşire $sakura.out$ ...
h2. Restricţii
* $1 ≤ T ≤ 10$
* $1 ≤ N, M ≤ 500$
* Pentru $20%$ din teste $N, M ≤ 13$
* Pentru $60%$ din teste $N, M ≤ 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
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. sakura.in |_. sakura.out |_. Explicatie |
| 2
4
0 1
0 2
3 1
2
0 1
1
2
0 1
| 2
-1
| 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.
|
table(example). |_. sakura.in |_. sakura.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="sakura") ==
