Knjigalica 

Društvene mreže na Internetu su prestale biti novost i postale su deo svakodnevice. Jedan od 
zanimljivijih fenomena koji su primetili članovi društvene mreže Knjigalica je brz porast broja 
prijateljstava. U skladu s onom starom poslovicom "prijatelj mog prijatelja moj je prijatelj" većina ljudi 
jednom dnevno pro]e kroz sve svoje prijatelje te svakog njihovog prijatelja dodaje u svoj skup 
prijatelja. Potreban je jedan dan da se novostvorena prijateljstva potvrde, pa tako ako su osobe A i B 
prijatelji, na dan X osoba A vidi samo potvrđena prijateljstva osobe B, dakle ona nastala prije tog 
dana. 
Sva prijateljstva su dvosmerna, ako je A prijatelj B, tada je i B prijatelj A. 
Kako društvena mreža Knjigalica još nije uvela mogućnost brisanja prijatelja, u jednom trenutku će svi 
biti prijatelji svima. Napišite program koji će odrediti nakon koliko dana će svi korisnici međusobno 
biti prijatelji. Za svaki dan ispišite koliko novih prijateljstava će se stvoriti taj dan. 

ULAZNI PODACI 
U prvom redu nalaze se prirodni brojevi N i M (1 ≤ N ≤ 50, 1 ≤ M ≤ N*(N–1)/2), broj registrovanih 
korisnika i početni broj prijateljstava. 
U sledećih M redova nalazi se popis početnih prijateljstava. U svakom redu nalaze se dva broja, A i B 
(1 ≤ A ≤ N, 1 ≤ B ≤ N, A < B), koji opisuju prijateljstvo između osobe A i osobe B. Ulazni podaci 
nikad neće sadržavati isto prijateljstvo više od jednom. Takođe, ulazni podaci će biti takvi da će 
rešenje uvek postojati. 

IZLAZNI PODACI 
U prvi red potrebno je ispisati jedan prirodni broj, broj dana nakon kojih će svi korisnici međusobno 
biti prijatelji. 
U svakom od nekoliko sledećih redova ispišite po jedan prirodni broj, broj prijateljstava nastalih taj 
dan.

Ulaz       Ulaz     Ulaz
3 2        5 4      5 4
1 2        1 2      1 2
2 3        2 3      1 3
           3 4      1 4
Izlaz      4 5      1 5
1           
1          Izlaz    Izlaz
           2        1
           3        6
           3