#pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define f(i,a,b) for(ll i=a;i<=b;i++)
ll read(){
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
#define d read()
ll n,m;
ll fa[1000010];
ll find(ll x){if(fa[x]==x)return x;return find(fa[x]);}
ll f[100010];
ll fnd(ll x){if(f[x]==x)return x;return f[x]=fnd(f[x]);}
ll x[1000010],y[1000010],de[1000010];
ll U[1000010],V[1000010];
#define pb push_back
bitset<5010>dp;
ll num[100010];
vector<ll>e;
bool eq[100010];
bool ch(){
    ll s=0;dp.reset();dp[0]=1;e.clear();
    f(i,1,2*n){ll t;
        if(eq[i])t=i;
        else if(eq[i+2*n])t=i+2*n;
        else continue;
        s+=min(x[t],y[t]);
        if(x[t]==y[t])continue;
        num[abs(x[t]-y[t])]++;
        if(num[abs(x[t]-y[t])]==1)e.pb(abs(x[t]-y[t]));
    }
    // cout<<n<<" "<<s<<" "<<num[1]<<endl;
    if(n-s-num[1]<=0){
        for(int i=0;i<e.size();i++){
            num[e[i]]=0;
        }
        return 1;
    }
    for(int i=0;i<e.size();i++){
        ll t=e[i];ll o=1;
        if(t==1)continue;
        while(o<=num[t]){
            dp|=dp<<(o*t);num[t]-=o;
            o*=2;
        }if(num[t])dp|=dp<<(num[t]*t);
        num[t]=0;
    }
    // 判断dp[n-s]到dp[n-s-num[1]]中是否有1
    ll t=num[1];num[1]=0;
    for(int i=n-s;i>=n-s-t;i--)if(dp[i])return 1;
    return 0;
    // return dp[n-s];
}
ll is[1000010];
bool in[1000010];
ll pre[1000010];
ll deg[100010];
map<pair<ll,ll>,bool>mp;
bool qw;
int main(){
    n=d,m=d;
    ll cl=clock();
    if(n+m==1005000-1)qw=1;
    f(i,1,2*n)fa[i]=i,x[i]=1,eq[i]=1,f[i]=i;
    f(i,2*n+1,4*n)fa[i]=i,y[i]=1,eq[i]=1;
    f(i,1,m){
        // if(i<=n)U[i]=1,V[i]=i+2*n;
        // else U[i]=i-n,V[i]=4*n;
        // U[i]=rand()%(2*n)+1,V[i]=rand()%(2*n)+1;
        // while(U[i]==V[i])V[i]=rand()%(2*n)+1;
        // mp[U[i]][V[i]]=1,mp[V[i]][U[i]]=1;
        // cout<<U[i]<<" "<<V[i]<<endl;
        U[i]=d,V[i]=d;
    }
    ll qwq=0;
    if(V[1]==9713)qw=1;else qw=0;
    for(int i=m;i>=1;i--){
        ll u=U[i],v=V[i];
        // if(mp[{u,v}])continue;
        // mp[{u,v}]=1,mp[{v,u}]=1;
        if(fnd(u)==fnd(v))continue;
        if(find(u)==find(v)||find(u)==find(v+2*n)||deg[u]==n||deg[v]==n)continue;
        f[fnd(u)]=fnd(v);
        ll fu=find(u),fv=find(v),fuu=find(u+2*n),fvv=find(v+2*n);
        ll oux=x[fu],ouy=y[fu],ovx=x[fv],ovy=y[fv],oude=de[fu],ovde=de[fv];
        ll ouux=x[fuu],ouuy=y[fuu],ovvx=x[fvv],ovvy=y[fvv],ouude=de[fuu],ovvde=de[fvv];
        ll ou=fa[u],ov=fa[v],ouu=fa[u+2*n],ovv=fa[v+2*n];
        ll oueq=eq[fu],oveq=eq[fv],ouueq=eq[fuu],ovveq=eq[fvv];
        ll uu=fuu,vv=fvv;u=fu,v=fv;
        if(de[uu]>de[v])swap(uu,v);
        fa[uu]=v,x[v]=x[uu]+x[v],y[v]=y[uu]+y[v],de[v]=max(de[v],de[uu]+1);eq[uu]=0;
        if(de[u]>de[vv])swap(u,vv);
        fa[u]=vv,x[vv]=x[u]+x[vv],y[vv]=y[u]+y[vv],de[vv]=max(de[vv],de[u]+1);eq[u]=0;

        if(qw&&i<=982809)cout<<i<<" "<<(clock()-cl)/(double)CLOCKS_PER_SEC<<endl;
        if(ch()){deg[u]++,deg[v]++;
            // e[U[i]].pb(V[i]);
            // e[V[i]].pb(U[i]);
            qwq++;
            // cout<<U[i]<<" " <<V[i]<<endl;
            if(qw&&qwq>=8280){
                cout<<qwq<<" "<<i<<" "<<U[i]<<" "<<V[i]<<endl;
                //输出从开始到现在的运行时间转化成毫秒
                cout<<(clock()-cl)/(double)CLOCKS_PER_SEC<<endl;

            }
            continue;
        }
        u=U[i],v=V[i];
        x[fu]=oux,y[fu]=ouy,x[fv]=ovx,y[fv]=ovy;
        x[fuu]=ouux,y[fuu]=ouuy,x[fvv]=ovvx,y[fvv]=ovvy;
        fa[u]=ou,fa[v]=ov,fa[u+2*n]=ouu,fa[v+2*n]=ovv;
        de[fu]=oude,de[fv]=ovde,de[fuu]=ouude,de[fvv]=ovvde;
        eq[fu]=oueq,eq[fv]=oveq,eq[fuu]=ouueq,eq[fvv]=ovveq;
    }
    if(qw)puts("111");
    return 0;
    ll s=0;in[0]=1;
    f(i,1,2*n){ll t;
        if(find(i)==i)t=i;
        else if(find(i+2*n)==i+2*n)t=i+2*n;
        else continue;
        s+=min(x[t],y[t]);ll q=abs(x[t]-y[t]);
        for(int j=n-q;j>=0;j--)if(!in[j+q]&&in[j]){
            in[j+q]=1;pre[j+q]=t;
        }if(x[t]<=y[t])is[t]=1;else is[t]=2;
    }s=n-s;
    // puts("222");
    while(1){
        ll p=pre[s];is[p]=3-is[p];
        s-=abs(x[p]-y[p]);
        if(s<=0)break;
    }
    // puts("333");
    f(i,1,2*n){
        if(is[find(i)]==1||is[find(i+2*n)]==2)cout<<0;
        else cout<<1;
    }
    return 0;
}
/*
2 4
2 4
4 2
1 2
2 3
*/