== include(page="template/taskheader" task_id="sakura") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $sakura.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $sakura.out$ ...
Î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"_.
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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
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.
|
== include(page="template/taskfooter" task_id="sakura") ==
