Code Submission Evaluation System Login

Datatähti-valmennus

Porukat


Task | Statistics


CSES - Porukat

Time limit:1.00 s Memory limit:128 MB

Uolevin luokalla on $n$ oppilasta. Vuoden alussa kukaan ei tunne toista, mutta oppilaat alkavat ystävystyä. Merkintä $a \leftrightarrow b$ tarkoittaa, että oppilaat $a$ ja $b$ ovat ystäviä.

Pikkuhiljaa luokkaan alkaa myös muodostua porukoita. Oppilaat $a$ ja $b$ kuuluvat samaan porukkaan, jos on olemassa ketju $a \leftrightarrow x_1 \leftrightarrow x_2 \leftrightarrow \cdots \leftrightarrow x_k \leftrightarrow b$.

Tehtäväsi on laskea porukoiden määrä jokaisen uuden ystävyyden jälkeen.

Syöte

Syötteen alussa on kaksi kokonaislukua $n$ ja $m$: oppilaiden määrä ja ystävyyksien määrä.

Sitten syötteessä on $m$ riviä, joista jokainen kuvaa ystävyyden. Rivillä on kaksi kokonaislukua $a$ ja $b$: oppilaat $a$ ja $b$ ystävystyvät.

Oppilas ei voi ystävystyä itsensä kanssa, ja samat kaksi oppilasta eivät voi ystävystyä useita kertoja.

Tuloste

Tulosta jokaisen ystävyyden jälkeen porukoiden määrä.

Rajat
Esimerkki

Syöte:
5 4
1 2
1 3
2 3
4 5


Tuloste:
4 3 3 2