#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=1e3+1;
const int MAXM=2e5+3;
int n,m,ans[MAXM],cnt;
pii e[MAXM];
struct Dynamic_Graph
{
    bitset<MAXN> vis[2][MAXN],g[MAXN];
    Dynamic_Graph *rev;
    inline void init()
    {
        for(int i=1;i<=n;i++)
            vis[0][i].set(i),vis[1][i].set(i),g[i].set(i);
    }
    inline void bfs(int s,int t)
    {
        static queue<int> q;
        static bitset<MAXN> tmp;
        q.push(t);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            tmp=g[u]&~vis[0][s];
            for(int v=tmp._Find_next(s-1);v<=n;v=tmp._Find_next(v))
                vis[0][s].set(v),vis[1][v].set(s),cnt+=rev->vis[0][s][v],q.push(v);
        }
    }
    inline void add(int s,int t)
    {
        static bitset<MAXN> tmp;
        g[s].set(t);
        tmp=vis[1][s]&~vis[1][t];
        for(int i=tmp._Find_first();i<=t;i=tmp._Find_next(i))
            vis[0][i].set(t),vis[1][t].set(i),cnt+=rev->vis[0][i][t],bfs(i,t);
    }
} nor,rev;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&e[i].first,&e[i].second);
    nor.rev=&rev,rev.rev=&nor;
    ans[m]=cnt=n;
    nor.init(),rev.init();
    for(int i=m;i>=1;i--)
    {
        nor.add(e[i].first,e[i].second);
        rev.add(e[i].second,e[i].first);
        // for(int j=1;j<=n;j++)
        //     ans[i-1]+=(nor.vis[0][j]&rev.vis[0][j]).count();
        ans[i-1]=cnt;
    }
    for(int i=0;i<=m;i++)
        printf("%d ",ans[i]);
    return 0;
}