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

#define int long long

const int N=5e5+1e3+7;

struct T{
    int l,r,ls,rs;
    int mn,cnt;
    int tag;
}t[N*2+1];

void add(int x,int v)
{
    t[x].tag+=v;
    t[x].mn+=v;
}

void pushdown(int x)
{
    if(!t[x].tag)
        return;
    add(t[x].ls,t[x].tag);
    add(t[x].rs,t[x].tag);
    t[x].tag=0;
}

void update(int x)
{
    t[x].mn=min(t[t[x].ls].mn,t[t[x].rs].mn);
    t[x].cnt=(t[t[x].ls].mn==t[x].mn)*t[t[x].ls].cnt+(t[t[x].rs].mn==t[x].mn)*t[t[x].rs].cnt;
}

int cnt;

int build(int l,int r)
{
    int x=++cnt;
    t[x].l=l,t[x].r=r;
    if(l==r)
    {
        t[x].cnt=1;
        return x;
    }
    int mid=(l+r)>>1;
    t[x].ls=build(l,mid);
    t[x].rs=build(mid+1,r);
    update(x);
    return x;
}

void change(int x,int l,int r,int v)
{
    if(l<=t[x].l&&t[x].r<=r)
    {
        add(x,v);
        return;
    }
    int mid=(t[x].l+t[x].r)>>1;
    if(l<=mid)
        change(t[x].ls,l,r,v);
    if(r>mid)
        change(t[x].rs,l,r,v);
    update(x);
}

vector<pair<int,int> > v[N*4];

void ins(int x,int l,int r,int L,int R,int a,int b)
{
    if(l>R||r<L)
        return;
    if(L<=l&&r<=R)
    {
        v[x].push_back({a,b});
        return;
    }
    int mid=(l+r)>>1;
    ins(x<<1,l,mid,L,R,a,b);
    ins(x<<1|1,mid+1,r,L,R,a,b);
}

int ans[N];

int fa[N],sz[N],mx[N],mn[N],w[N];

int find(int x)
{
    return x==fa[x]?x:find(fa[x]);
}

int now=0;

void solve(int x,int l,int r)
{
    vector<pair<int*,int> >modify;
    int ln=now;
    for(auto [a,b]:v[x])
    {
        change(1,a,b-1,1);
        int A=find(a),B=find(b);
        if(A!=B)
        {
            if(sz[A]>sz[B])
                swap(A,B);
            if(w[B]==(mx[B]-mn[B]+1)*(mx[B]-mn[B])/2)
                now-=mx[B]-mn[B];
            if(w[A]==(mx[A]-mn[A]+1)*(mx[A]-mn[A])/2)
                now-=mx[A]-mn[A];
            modify.emplace_back(&fa[A],fa[A]);
            fa[A]=B;
            modify.emplace_back(&sz[B],sz[B]);
            modify.emplace_back(&w[B],sz[B]);
            modify.emplace_back(&mx[B],sz[B]);
            modify.emplace_back(&mn[B],sz[B]);
            sz[B]+=sz[A];
            w[B]+=w[A];
            mx[B]=max(mx[B],mx[A]);
            mn[B]=min(mn[B],mn[A]);
        }
        modify.push_back({&w[B],w[B]});
        w[B]++;
        if(w[B]==(mx[B]-mn[B]+1)*(mx[B]-mn[B])/2)
            now+=mx[B]-mn[B];
    }
    if(l==r)
    {
        ans[l]=now+(t[1].mn==0)*t[1].cnt+1;
        for(auto [a,b]:v[x])
            change(1,a,b-1,-1);
        reverse(modify.begin(),modify.end());
        for(auto [x,y]:modify)
            *x=y;
        now=ln;
        return;
    }
    int mid=(l+r)>>1;
    solve(x<<1,l,mid);
    solve(x<<1|1,mid+1,r);
    
    for(auto [a,b]:v[x])
        change(1,a,b-1,-1);
    reverse(modify.begin(),modify.end());
    for(auto [x,y]:modify)
        *x=y;
    now=ln;
}

int n,q;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    build(1,n-1);
    map<pair<int,int>,int >mp,la;
    for(int i=1;i<=n;i++)
        fa[i]=i,sz[i]=1,mx[i]=i,mn[i]=i;
    for(int i=1;i<=q;i++)
    {
        int u,v;
        cin>>u>>v;
        mp[{u,v}]^=1;
        if(mp[{u,v}]==0)
        {
            ins(1,1,q,la[{u,v}],i-1,u,v);
            la[{u,v}]=0;
        }
        else
            la[{u,v}]=i;
    }
    for(auto [x,y]:mp)
        if(y==1)
            ins(1,1,q,la[x],q,x.first,x.second);
    solve(1,1,q);
    for(int i=1;i<=q;i++)
        cout<<ans[i]<<"\n";
}