#include<bits/stdc++.h>
using namespace std;
const int N=5e3,M=1e6;
const int mod=998244353;
int add(int x,int y){ return (x+=y)>=mod?x-mod:x; }
int sub(int x,int y){ return (x-=y)<0?x+mod:x; }
int n,m;
int a[M+5],b[M+5];
bool ok[N+5][N*2+5];
int f[N*2+5],sz[N*2+5],sid[N*2+5];
int dp[N+5],ms;
void insert(int x){
    ms+=x;
    for(int j=n;j>=x;j--)
        dp[j]=add(dp[j],dp[j-x]);
}
void del(int x){
    if(x==0){
        for(int j=0;j<=n;j++)
            dp[j]=1ll*dp[j]*(mod+1)/2%mod;
    }
    else{
        for(int j=x;j<=n;j++)
            dp[j]=sub(dp[j],dp[j-x]);
    }
    ms-=x;
}
int find(int x){ return x==f[x]?x:f[x]=find(f[x]); }
void check(int u,int v){
    int fu=find(u),fv=find(v);
    int su=sz[fu],sv=sz[fv],tp=sid[u]==sid[v];
    if(tp) sv=-sv;
    if(ok[su][sv+N]||(fu==fv&&tp)) return;
    static int pre[N+5];
    memcpy(pre,dp,sizeof dp);
    del(su); del(abs(sv));
    // for(int i=0;i<=ms;i++)
    //     printf("%d ",dp[i]);
    // puts("");
    insert(abs(su+sv));
    // printf("%d %d %d\n",su,sv,ms);
    if(dp[ms/2]){
        // printf("%d %d\n",u,v);
        if(su+sv>0){
            for(int i=1;i<=n*2;i++)
                if(find(i)==fv) sid[i]^=tp;
            f[fv]=fu; sz[fu]=su+sv;
        }
        else{
            for(int i=1;i<=n*2;i++)
                if(find(i)==fu) sid[i]^=tp;
            f[fu]=fv; sz[fv]=-(su+sv);
        }
        return;
    }
    else{
        ms-=abs(su+sv);
        ms+=su+abs(sv);
        memcpy(dp,pre,sizeof dp);
        ok[su][sv+N]=1;
    }
}
void work(){
    static int g[N+5],pre[N*2+5][N+5];
    g[0]=1;
    for(int i=1;i<=n*2;i++){
        for(int j=0;j<=ms/2;j++)
            if(g[j]) pre[i][j]=j;
        if(find(i)==i){
            int x=sz[i];
            for(int j=ms/2;j>=x;j--)
                if(!g[j]&&g[j-x]){
                    g[j]=1; pre[i][j]=j-x;
                }
        }
    }
    static char ans[N*2+5];
    for(int i=1;i<=n*2;i++)
        ans[i]='0';
    for(int i=n*2,j=ms/2;i;i--){
        if(find(i)==i){
            if(pre[i][j]!=j){
                for(int u=1;u<=n*2;u++)
                    if(find(u)==i&&sid[u])
                        ans[u]='1';
            }
            else{
                for(int u=1;u<=n*2;u++)
                    if(find(u)==i&&!sid[u])
                        ans[u]='1';
            }
            j=pre[i][j];
        }
    }
    printf("%s\n",ans+1);
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d %d",&a[i],&b[i]);
    dp[0]=1;
    for(int i=1;i<=n*2;i++){
        f[i]=i; sz[i]=1; sid[i]=0;
        insert(1);
    }
    for(int i=m;i;i--)
        check(a[i],b[i]);
    work();
    return 0;
}