Se consideră un graf neorientat cu n vârfuri și m muchii. Cele m muchii se elimină pe rând din graf.

Cerința

Pentru fiecare muchie eliminată trebuie să spuneți câte componente conexe are graful.

Date de intrare

Programul citește de la tastatură numerele n și m, iar pe următoarele m linii se află câte două valori x și y separate prin spațiu, reprezentând o muchie din graf. Muchiile vi se dau în ordinea în care ele se elimină din graf.

Date de ieșire

Programul va afișa pe ecran exact m linii, pe fiecare linie i aflându-se un singur număr natural reprezentând numărul componentelor conexe din graf după eliminarea celei de-a i-a muchii.

Restricții și precizări

• 1 ≤ n ≤ 100 000
• 1 ≤ m ≤ 500 000
• Între două vârfuri va exista cel mult o muchie

Exemplu

Intrare

5 6
1 2
3 4
2 3
1 5
5 4
4 1

Ieșire

1
2
3
3
4
5

Explicație

Sunt 5 vârfuri și 6 muchii. Urmează cele 6 muchii în ordinea eliminării lor. După eliminarea muchiei 1 2 graful este tot conex, deci rezultatul este 1. După eliminarea muchiei 3 4 se obțin două componente conexe, una formată din vârfurile 2, 3, iar cealaltă componentă formată din vârfurile 1, 4, 5. Restul eliminărilor nu mai trebuie explicate că ați înțeles deja.

#include <bits/stdc++.h>
using namespace std;

int n , m , x , y , T[500001] , cnt , rez[500001];
struct poz
{
    int i , j;
}M[500001];

void leaga(int a , int b)
{
    if(T[a] > T[b]) T[a] = T[b];
    else T[b] = T[a];
}

int radacina(int a)
{
    if(a == T[a]) return a;
    else return T[a] = radacina(T[a]);
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y;
        M[i].i = x;
        M[i].j = y;
    }
    for(int i = 1 ; i <= n ; i++) T[i] = i;
    rez[++cnt] = n;
    for(int i = m ; i > 1 ; i--)
    {
        if(radacina(M[i].i) != radacina(M[i].j))
        {
            leaga(radacina(M[i].i) , radacina(M[i].j));
            n--;
            rez[++cnt] = n;
        }
        else rez[++cnt] = n;
    }

    for(int i = cnt ; i >= 1 ; i--)
        cout << rez[i] << '\n';
}