#include <cstdio>

#include <algorithm>

#define maxn 800010

int n,m,ai[maxn][],bi[maxn],f[maxn<<],st[maxn];

int g[maxn],nxt[maxn<<],q[maxn<<],t,ans[maxn],L,x,y,i;

inline void in(int&a)

{

    char c;

    while(!(((c=getchar())>='')&&(c<='')));

    a=c-'';while(((c=getchar())>='')&&(c<=''))(a*=)+=c-'';

}

inline int lower(int x)

{

    int l=,r=m,mid,t;

    while(l<=r) if(bi[mid=(l+r)>>]<=x) l=(t=mid)+;else r=mid-;

    return t;

}

inline void up(int &x,int y)

{

    if(x<y) x=y;

}

void dfs(int x)

{

    q[++t]=x;

    if(x<=m)

        for(int i=L;;i++)

            if(q[t-i]>=x+m)

            {

                ans[x]=i;

                break;

            }

    for(int i=g[x];i;i=nxt[i]) dfs(i);

    t--;

}

int main()

{

    freopen("data.txt","r",stdin);

    in(n),in(m);

    for(m=,i=;i<=n;i++) in(ai[i][]),in(ai[i][]),bi[++m]=ai[i][],bi[++m]=ai[i][];

    for(std::sort(bi+,bi+m+),i=;i<=n;i++)

    {

        st[i]=x=lower(ai[i][]),y=lower(ai[i][]);

        if(x<y) up(f[x],y),up(f[x+m],y+m);

        else up(f[],y),up(f[x],y+m),up(f[x+m],m+m);

    }

    for(i=;i<=m+m;i++) up(f[i],f[i-]);

    for(i=;i<m+m;i++) nxt[i]=g[f[i]],g[f[i]]=i;

    for(L=-,i=;i<=m;i=f[i])L++;

    dfs(m+m);

    for(i=;i<=n;i++) printf("%d ",ans[st[i]]);

    return ;

}