#include<bits/stdc++.h>
#include <immintrin.h>
using namespace std;
const int N=5005,M=1000005;
int n,m;
int a[M],b[M];
int fa[N*4];
int siz[N*4];
int num[N*4][2];
int getf(int v)
{
    if(v==fa[v]) return v;
    else return fa[v]=getf(fa[v]);
}
void merge(int u,int v)
{
    int fu=getf(u),fv=getf(v);
    if(fu!=fv)
    {
        num[fu][0]+=num[fv][(fu>n*2)^(fv>n*2)];
        num[fu][1]+=num[fv][(fu>n*2)^(fv>n*2)^1];
        fa[fv]=fu;
    }
    return;
}
vector<pair<int,int>>G[N*2];
int col[N*2];
bitset<N>f[N*2];
int rt[N*2],c[N*2][2];
void dfs(int u,int color)
{
    col[u]=color;
    for(auto [v,w]:G[u])
        if(col[v]==-1) dfs(v,color^w);
    return;
}
multiset<int>val;
int sum=0;
int cnt0=0;
void erase(int c0,int c1)
{
    if(c0>c1) swap(c0,c1);
    sum-=c0;
    if(c0==c1) return;
    if(c1-c0==1)
    {
        cnt0--;
        return;
    }
    val.erase(val.lower_bound(c1-c0));
    return;
}
void insert(int c0,int c1)
{
    if(c0>c1) swap(c0,c1);
    sum+=c0;
    if(c0==c1) return;
    if(c1-c0==1)
    {
        cnt0++;
        return;
    }
    val.insert(c1-c0);
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i]>>b[i];
    for(int i=1;i<=n*4;i++)
        fa[i]=i,num[i][0]=1;
    cnt0=n*2;
    int cnt[2];
    for(int i=m;i>=1;i--)
    {
        int u=a[i],v=b[i];
        if(getf(u)==getf(v)||getf(u+n*2)==getf(v+n*2)) continue;
        if(getf(u)==getf(v+n*2)||getf(u+n*2)==getf(v)) continue;
        u=getf(u),v=getf(v);
        int w=1;
        int cu[2]={num[u][0],num[u][1]};
        erase(cu[0],cu[1]);
        int cv[2]={num[v][0],num[v][1]};
        erase(cv[0],cv[1]);
        if(u>n*2) w^=1,u-=n*2;
        if(v>n*2) w^=1,v-=n*2;
        cnt[0]=cu[0]+cv[w],cnt[1]=cu[1]+cv[w^1];
        insert(cnt[0],cnt[1]);
        if(cnt[0]>cnt[1]) swap(cnt[0],cnt[1]);
        bool flag=true;
        if(sum>n) flag=false;
        if(flag)
        {
            int ret=n-sum;
            bitset<N> f;
            f.set(0);
            for(auto c01:val)
            {
                f|=f<<c01;
                if(f[ret]) break;
            }
            flag=false;
            for(int j=0;j<=cnt0;j++)
                if(f[ret-j])
                {
                    flag=true;
                    break;
                }
        }
        if(!flag)
        {
            erase(cnt[0],cnt[1]);
            cnt[0]=cu[0]+cv[w^1],cnt[1]=cu[1]+cv[w];
            insert(cnt[0],cnt[1]);
            if(w)
            {
                merge(u,v);
                merge(u+n*2,v+n*2);
            }
            else
            {
                merge(u,v+n*2);
                merge(u+n*2,v);
            }
            G[u].emplace_back(v,w^1);
            G[v].emplace_back(u,w^1);
            continue;
        }
        G[u].emplace_back(v,w);
        G[v].emplace_back(u,w);
        if(w)
        {
            merge(u,v+n*2);
            merge(u+n*2,v);
        }
        else
        {
            merge(u,v);
            merge(u+n*2,v+n*2);
        }
    }
    fill(col+1,col+n*2+1,-1);
    f[0][0]=1;
    int tot=0;
    for(int u=1;u<=n*2;u++)
    {
        if(col[u]==-1)
        {
            cnt[0]=cnt[1]=0;
            dfs(u,0);
            rt[++tot]=u;
            c[tot][0]=cnt[0],c[tot][1]=cnt[1];
            f[tot]=(f[tot-1]<<cnt[0])|(f[tot-1]<<cnt[1]);
        }
    }
    assert(f[tot][n]);
    fill(col+1,col+n*2+1,-1);
    int ret=n;
    for(int i=tot;i>=1;i--)
    {
        int u=rt[i];
        if(ret>=c[i][0]&&f[i-1][ret-c[i][0]])
        {
            ret-=c[i][0];
            dfs(u,0);
        }
        else
        {
            ret-=c[i][1];
            dfs(u,1);
        }
    }
    for(int u=1;u<=n*2;u++)
        cout<<col[u];
    return 0;
}