$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.

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 strategii 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.