Compaq Computer Romania

În curtea unei case se află M arbori binari. Într-o zi, proprietarul a primit de la un prieten o fotografie cu N arbori binari. Poza i-a plăcut atât de mult, încât a decis să transforme N dintre arborii din grădină în cei N arbori din poză, dacă este posibil. Dacă nu, el dorește să transforme un număr K dintre arborii din grădină în K arbori (cu numere de ordine diferite) din poză, maximizând valoarea K.
     Proprietarul poate tăia crengi ale arborilor din grădină. În final, doi arbori (unul din gradină, unul din poză) sunt identici dacă au aceeași configurație a crengilor (muchiilor); numerele care identifică nodurile sunt ignorate. Mai multe detalii reies din studierea exemplului.
     Trebuie să scrieți un program pentru a-l ajuta pe proprietar să minimizeze numărul crengilor tăiate, în condițiile în care numărul K, definit anterior, este maxim.

Pe prima linie a fișierului de intrare se află valorile M și N, separate printr-un singur spațiu.
     În continuare sunt descriși cei M arbori din curte. Pe prima linie corespunzătoare unui arbore se află numărul X al nodurilor arborelui. Fiecare dintre următoarele linii descriu fiii fiecărui nod din arbore. Prima linie corespunde primului nod (care este întotdeauna rădăcina arborelui), a doua celui de-al doilea nod etc. Fiecare linie conține două numere cuprinse între 0 și X și indică numărul de ordine al celor doi fii ai nodului corespunzător liniei. Valoarea 0 indică faptul că nodul respectiv nu există.
     Urmează descrierile celor N arbori din poză. Aceștia sunt descriși în același mod ca și cei M arbori din curte.
     Datele de intrare sunt corecte; se garantează că fiecare descriere corespunde unui arbore binar.

Pe prima linie a fișierului de ieșire se va afla numărul K al arborilor care pot fi obținuți. Pe a doua linie se află numărul MIN al crengilor tăiate.
     Pe fiecare dintre următoarele K linii se va afla o pereche de numere: număr_arbore_curte, număr_arbore_poză care indică faptul că arborele număr_arbore_poză se obține tăind crengi din arborele număr_arbore_curte. Numerele de ordine ale arborilor din curte care apar în fișierul de ieșire trebuie să fie distincte. Similar, numerele de ordine ale arborilor din poză care apar în fișierul de ieșire trebuie să fie distincte. Nu contează ordinea în care sunt scrise perechile în fișierul de ieșire, iar dacă există mai multe soluții se va afișa una singură.

· 1 <= M, N <= 40;
· doi arbori nu se consideră identici decât dacă subarborii lor drepți sunt identici și subarborii lor stângi sunt identici; dacă cei doi arbori sunt simetrici (subarborele stâng al unuia este identic cu subarborele drept al celuilalt și invers) atunci ei nu sunt considerați identici;
· fiecare arbore are cel mult 100 de noduri.

TREES.IN
3 3
2
2 0
0 0
3
2 3
0 0
0 0
5
5 3
0 0
0 0
0 0
4 2
3
3 2
0 0
0 0
2
0 2
0 0
3
2 0
0 3
0 0

TREES.OUT
2
1
2 1
3 2