//Linkwish's code
#include<bits/stdc++.h>
#define endl '\n'
#define si inline
#define fi first
#define se second
using namespace std;
typedef long long ll;typedef __int128 li;typedef long double ld;
typedef pair<int,int> pii;typedef pair<ll,ll> pll;typedef unsigned long long ull;
typedef const int ci;typedef const ll cl;ci iinf=INT_MAX;cl linf=LLONG_MAX;
template<typename T>si bool gmax(T &x,const T y){if(x<y)return x=y,1;return 0;}
template<typename T>si bool gmin(T &x,const T y){if(y<x)return x=y,1;return 0;}

namespace LinkWish{

	ci N=5005,M=1000005,U=20005;

	int n,m;
	int a[M],b[M];

	int fa[U],sz[U];
	pii stk[U];int top;
	int getf(int x){while(x!=fa[x])x=fa[x];return x;}
	si void merge(int x,int y){
		if((x=getf(x))==(y=getf(y)))return ;
		if(sz[x]<sz[y])swap(x,y);
		sz[x]+=sz[y],fa[y]=x,stk[++top]=pii(x,y);
	}
	si void back(int ver){
		while(top>ver){
			int x=stk[top].fi,y=stk[top].se;
			top--,fa[y]=y,sz[x]-=sz[y];
		}
	}

	int p[U],id1[U],id2[U],num,sum;
	bool vis[U];

	int t[U];
	si void reid(bool flag=0){
		sum=num=0;
		vector<int> all;
		for(int i=1,x,y;i<=2*n;i++){
			x=getf(i);
			if(!vis[x]){
				y=getf(i+2*n);
				all.push_back(x),all.push_back(y),vis[x]=vis[y]=1;
				if(sz[x]<sz[y])swap(x,y);
				p[++num]=sz[x]-sz[y],sum+=sz[y];
				id1[num]=x,id2[num]=y;
			}
		}
		for(int i:all)vis[i]=0;

		if(flag){
			for(int i=1;i<=num;i++)t[p[i]]++;
			num=0;
			for(int i=1;i<=2*n;i++){
				if(t[i]){
					int c=1;
					for(;t[i]>c;c<<=1)t[i]-=c,p[++num]=c*i;
					p[++num]=c*i,t[i]=0;
				}
			}
		}
	}

	template<int NN=1>
	si bool check(){
		if(NN<=n-sum)return check<min(NN*2,N)>();
		reid(1);
		bitset<NN> f;
		f[0]=1;
		for(int i=1;i<=num;i++)f|=(f<<p[i]);
		return f[n-sum];
	}

	int f[N][N];
	bool ans[U<<1];
	si void outp(){
		reid();

		f[0][0]=1;
		for(int i=1;i<=num;i++){
			for(int j=0;j<=n-sum;j++){
				if(f[i-1][j])f[i][j]=-1;
				else if(j>=p[i]&&f[i-1][j-p[i]])f[i][j]=1;
			}
		}

		assert(f[num][n-sum]);

		for(int i=num,cur=n-sum;i;i--){
			int x=id1[i],y=id2[i];
			if(f[i][cur]==-1)ans[x]=0,ans[y]=1;
			else ans[x]=1,ans[y]=0,cur-=p[i];
		}

		for(int i=1;i<=2*n;i++)cout<<ans[getf(i)];
		cout<<endl;
	}

	void mian(){
		cin>>n>>m;
		for(int i=1;i<=m;i++)cin>>a[i]>>b[i];
		for(int i=1;i<=2*n;i++)fa[i]=i,sz[i]=1,fa[i+2*n]=i+2*n;

		for(int i=m;i;i--){
			int x=a[i],y=b[i];
			if(getf(x)==getf(y)||getf(x)==getf(y+2*n))continue;
			int tmp=top;
			merge(x,y+2*n),merge(x+2*n,y);
			if(!check()){
				back(tmp);
				merge(x,y),merge(x+2*n,y+2*n);
			}
			// cerr<<"MER "<<x<<' '<<y<<endl;
			// for(int j=1;j<=2*n;j++)cerr<<getf(j)<<' '<<getf(j+2*n)<<endl;
			// cerr<<endl;
		}

		outp();
	}
}

signed main(){
	#ifndef ONLINE_JUDGE
	assert(freopen("in.in","r",stdin));
	// assert(freopen("out.out","w",stdout));
	// assert(freopen("out.err","w",stderr));
	#endif
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);   
	LinkWish::mian();
	return 0;
}