brazi

Brazi

== include(page="template/taskheader" task_id="brazi") ==

Se dau N arbori binari, numerotati de la 1 la N. Pentru fiecare arbore i sa se afiseze cati arbori din primii i-1 sunt izomorfi cu el.

Anul acesta brazii au forma unor arbori binar. Un brad este identificat prin numarul de noduri $N$ si $N-1$ muchii care pot fi de doua tipuri:
 
* $x y 0$ insemnand ca $y$ este fiul stang al lui $x$
* $x y 1$ insemnand ca $y$ este fiul drept al lui $x$
 
Doi brazi sunt asemenea daca, schimband etichetarea unuia dintre ei, se obtin fix muchiile celuilalt.
 
De exemplu: bradul 1 2 0, 1 3 1, 2 4 0 nu este asemenea cu bradul 1 2 1, 1 3 0, 2 4 1 dar este asemenea cu 1 3 0, 1 2 1, 3 4 0.
 
Se dau $T$ astfel de brazi care contin maxim 10 noduri. Pentru fiecare brad i, sa se afiseze numarul de brazi din primii $i-1$ care sunt asemenea cu el.

h2. Date de intrare

Fişierul de intrare $brazi.in$ ...

Fişierul de intrare $brazi.in$ contine pe prima linie un numar natural $T$, numarul de brazi. Fiecare brad este descris in $N$ linii. Pe prima se afla $N$, numarul de noduri. Pe urmatoarele $N-1$ se afla $3$ numere $x$ $y$ 0 sau $x$ $y$ 1 reprezentand o muchie a bradului.

h2. Date de ieşire

În fişierul de ieşire $brazi.out$ ...

În fişierul de ieşire $brazi.out$ va contine $T$ linii. Pe linia $i$ se va scrie numarul de brazi din primii $i-1$ care sunt asemenea cu bradul $i$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 100000$
* $1 ≤ N ≤ 10$
* $1 ≤ x, y ≤ N$

h2. Exemplu

table(example). |_. brazi.in |_. brazi.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
4
1 2 0
1 3 1
2 4 0
4
1 2 1
1 3 0
2 4 1
4
1 3 0
1 2 1
3 4 0
| 0
0
1

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="brazi") ==

9419