Fişierul intrare/ieşire:sakura.in, sakura.outSursăLot Râmnicu Vâlcea 2015 - Baraj 2 Seniori
AutorAndrei HeidelbacherAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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.

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

  • 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

Exemplu

sakura.insakura.outExplicatie
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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?