Knjigalica

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