==Include(page="template/taskheader" task_id="arbfind")==

==Include(page="template/raw")==
 
Se numeste arbore cu radacina o structura care contine un nod special denumit radacina arborelui si $A ~1~, A ~2~, ..., A ~n~$ (unde $n ≥ 0$) arbori cu radacina (denumiti subarbori ai radacinii). Nodul radacina al fiecarui arbore $A ~i~$ este denumit fiu al radacinii arborelui si este conectat printr-o muchie de radacina arborelui.

Se numeste arbore cu radacina o structura care contine un nod special denumit radacina arborelui si $A{~1~}, A{~2~}, ..., A{~n~}$ (unde $n ≥ 0$) arbori cu radacina (denumiti subarbori ai radacinii). Nodul radacina al fiecarui arbore $A{~i~}$ este denumit fiu al radacinii arborelui si este conectat printr-o muchie de radacina arborelui.

Doi arbori cu radacina sunt identici daca radacinile celor doi au acelasi numar de subarbori si acestia sunt identici (mai exact, pentru orice $i=1, 2, ..., n$ subarborele $i$ al primului este identic cu subarborele $i$ al celui de-al doilea).
O termita poate "ciopli" un arbore actionand astfel:

# termita porneste de la radacina arborelui;
# la fiecare moment (in orice nod s-ar afla), termita poate face una dintre urmatoarele operatii:

1. termita porneste de la radacina arborelui;
2. la fiecare moment (in orice nod s-ar afla), termita poate face una dintre urmatoarele operatii:

* sta in nod si mananca cea mai din dreapta muchie, eliminand astfel cel mai din dreapta fiu si subarborele corespunzator (acestea cad si vor fi mancate de alte termite lenese);
* inainteaza pe muchia din dreapta, spre fiul ramas cel mai din dreapta al nodului in care se afla;

h2. Date de Intrare

Pe prima linie a fisierului de intrare arbfind.in se gaseste un numar natural N reprezentand numarul de noduri din arborele model, nodurile fiind numerotate de la 1 la N. Pe liniile 2..N+1 se va afla descrierea arborelui model. Mai exact, pe linia i se va afla un numar natural F[i-1] reprezentand numarul de fii directi ai nodului i-1, urmat de F[i-1] numere naturale cuprinse intre 1 si N, reprezentand in ordinea de la stanga la dreapta fiii nodului i-1.

Pe prima linie a fisierului de intrare $arbfind.in$ se gaseste un numar natural $N$ reprezentand numarul de noduri din arborele model, nodurile fiind numerotate de la $1$ la $N$. Pe liniile $2..N+1$ se va afla descrierea arborelui model. Mai exact, pe linia $i$ se va afla un numar natural $F{~i-1~}$ reprezentand numarul de fii directi ai nodului $i-1$, urmat de $F ~i-1~$ numere naturale cuprinse intre $1$ si $N$, reprezentand in ordinea de la stanga la dreapta fiii nodului $i-1$.

Linia N+2 va contine un numar natural M reprezentand numarul de noduri din arborele de evaluat. Liniile N+3..N+M+2 vor contine descrierea arborelui de evaluat, in mod analog cu descrierea arborelui model.

Linia $N+2$ va contine un numar natural $M$ reprezentand numarul de noduri din arborele de evaluat. Liniile $N+3..N+M+2$ vor contine descrierea arborelui de evaluat, in mod analog cu descrierea arborelui model.

h2. Date de Iesire

Fisierul de iesire arbfind.out va contine M linii. Pe linia i se va afla similaritatea subarborelui cu radacina in nodul i fata de arborele model.

Fisierul de iesire $arbfind.out$ va contine $M$ linii. Pe linia $i$ se va afla similaritatea subarborelui cu radacina in nodul $i$ fata de arborele model.

h2. Restrictii si precizari

Radacina arborilor este intotdeauna nodul 1.
 
1 <= M, N <= 32000

* Radacina arborilor este intotdeauna nodul $1$.
* $1 ≤ M, N ≤ 32000$

h2. Exemplu

table(example). |_. arbfind.in |_. arbfind.out |
| 4
2 2 3
1 4
0
0
9
2 2 3
2 4 5
2 6 7
1 8
0
0
1 9
0
0
| 3
4
2
2
1
1
2
1
1
|
 
h3. Explicatii

|arbfind.in |arbfind.out |Arbore model Arbore de evaluat |

!problema/arbfind?arbfind.jpg!

|4 |3 | |
| | | |
|2 2 3 |4 | |
| | | |
|1 4 |2 |De exemplu, pentru nodul 1 din arborele model s-au eliminat in ordine subarborii cu radacinile 3, 5 si 8. Din arborele model se elimina subarborele cu radacina 3. |
| | | |
|0 |2 | |
| | | |
|0 |1 | |
| | | |
|9 |1 | |
| | | |
|2 2 3 |2 | |
| | | |
|2 4 5 |1 | |
| | | |
|2 6 7 |1 | |
| | | |
|1 8 | | |
| | | |
|0 | | |
| | | |
|0 | | |
| | | |
|1 9 | | |
| | | |
|0 | | |
| | | |
|0 | | |

De exemplu, pentru nodul 1 din arborele model s-au eliminat in ordine subarborii cu radacinile 3, 5 si 8. Din arborele model se elimina subarborele cu radacina 3.
==Include(page="template/taskfooter" task_id="arbfind")==

==Include(page="template/taskfooter" task_id="arbfind")==

1103