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

Poveste si cerinta...

$N$ switch-uri, numerotate de la $1$ la $N$, sunt interconectate intr-o retea prin conexiuni din fibra optica. Reteaua are o structura arborescenta. Radacina arborelui este reprezentata de switch-ul numerotat cu $1$, pe care il consideram situat pe nivelul cel mai de sus din arbore. O conexiune leaga $2$ switch-uri si este unidirectionala (orientata de la switch-ul aflat pe un nivel superior catre cel aflat pe un nivel inferior). Switch-ul cu numarul $1$ trebuie sa transmita niste informatii foarte importante referitoare la starea retelei tuturor celorlalte switch-uri. Pentru a realiza acest lucru, trebuie stabilita o strategie inteligenta de broadcast (transmisie catre toate switch-urile).
 
La orice moment de timp, un switch $A$ care detine informatiile (initial, la momentul $0$, doar switch-ul $1$ detine informatiile) poate stabili o cale optica pana la un switch $B$ aflat in subarborele switch-ului $A$. Calea optica consta din switch-urile $A$, $B$ si toate celelalte switch-uri aflate pe drumul unic (si orientat) de la $A$ la $B$. Stabilirea caii optice dureaza $1$ unitate de timp, transmisia informatiilor realizandu-se apoi instantaneu. La finalul transmisiei pe calea optica stabilita, doar switch-ul $B$ va primi informatiile, nu si celelalte switch-uri intermediare de pe drumul de la $A$ la $B$. O restrictie suplimentara generata de modul de functionare al switch-urilor este ca, la orice moment de timp, orice switch poate face parte din cel mult o cale optica. Asadar, la fiecare moment de timp, caile optice stabilite pentru transmiterea informatiilor trebuie sa fie disjuncte din punct de vedere al switch-urilor ce fac parte din ele. Timpul de transmitere a informatiilor al unei strageii de broadcast este momentul de timp maxim la care unul din switch-uri a primit informatiile.
 
Determinati o strategie de broadcast cu timp minim de transmitere a informattilor.

h2. Date de intrare

...

Fisierul de intrare $optic.in$ contine, pe prima linie, numarul natural $N$, reprezentand numarul de switch-uri din retea. Urmatoarele $N-1$ linii contin cate doua numere naturale distincte $A$ si $B$ avand semnificatia ca exista o conexiune directa orientata de la $A$ la $B$.

h2. Date de iesire

...

Fisierul de iesire $optic.out$ va contine, pe prima linie, timpul minim $T$ de transmitere a informatiilor. In continuare, pentru fiecare moment de timp $M$ de la $0$ la $T-1$ va fi afisat un numar natural $C$, reprezentand numarul de cai optice stabilite la momentul $M$, urmat de $C$ linii continand $2$ numere naturale separate printr-un spatiu, $A$ si $B$, avand semnificatia ca s-a stabilit o cale optica de la switch-ul $A$ la switch-ul $B$, la momentul $M$, in vederea transmiterii informatiilor.

h2. Restrictii

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

* $1 ≤ N ≤ 333$

h2. Exemplu
table(example). |_. optic.in |_. optic.out |

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

|6
1 2
1 3
3 4
4 5
5 6
|3
1
1 3
2
1 2
3 5
2
3 4
5 6

|

h3. Explicatie
 
...
 

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