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