infoarena

Atunci când cineva trimite un mesaj, ceva misterios şi fascinant este transmis mai departe. Să zicem că Winettou vrea să transmită mesajul "Dansul Norilor, războiul s-a terminat. Winettou". Mai întâi îl dictează unui prieten, acesta aprinde un foc şi trimite acelaşi mesaj ca un tipar de semnale cu fum.  Dansul Norilor aflat la kilometri distanţă, se uită pe cer şi recepţionează exact acelaşi mesaj care îi fusese adresat.
   Înainte de-a fi cuceriţi, de europeni , indienii  trăiau pe suprafeţe foarte întinse şi foloseau acest minunat mod de-a comunica încă din timpuri străvechi. Un lucru extraordinar,  dacă trebuiau să retransmită mesajul mai departe nu-l modificau în niciun fel.
   Înţeleptii organizează întâlnirea anuală a indienilor pentru a-şi celebra zeul. Se întâlnesc, într-un anumit loc dinainte ales,  împreună cu câteva căpetenii de trib la "pipa pacii" şi hotărăsc data acestui important eveniment, în funcţie de astre şi de alte lucruri ştiute doar de ei. Căpeteniile se întorc, mergând fiecare 3 ore,  în ţinuturile lor. Odată ajunşi transmit după 10 minute mesajul folosind, bineînţeles,  fumul.  Mesajul este transmis  continuu fie zi, fie noapte. Din momentul în care o căpetenie de trib primeşte prima dată semnalul,  îl retransmite mai departe după 10 minute de la primire. Timpul de transmitere/descifrare a unui mesaj este de 5 minute.  Ştiind că numele indienilor este o poveste de viaţă, complicat pentru noi, ne vedem "nevoiţi"  să-l înlocuim printr-un număr. Mai este ceva, fumul poate fi văzut doar între anumite ţinuturi.

Cerinţă
Scrieţi un program care să calculeze timpul minim, în minute,  necesar pentru ca toate căpeteniile să fi primit mesajul.  Dacă nu se poate acest lucru atunci calculaţi câte căpetenii de trib nu au fost anunţate.
Exempu
8
2 //numarul de capeteni care au fost la intalnire
3 6 //capetenile care au fost la intalnire
1 2 //restul grafului...
1 3
1 6
2 4
3 4
3 5
3 6
6 7
6 8
7 8
raspuns: 210