#include <bits/stdc++.h>
using namespace std;
const int N=10005,M=1e6+5;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
int n,m,a[M],b[M],fa[N],s1[N],s2[N],p[N],tot,t[N],len,pre[N],ans[N],G[N];
vector<pair<int,int>>e[N];
inline void dfs(int x){
	for(auto[y,c]:e[x])ans[y]=ans[x]^c,dfs(y);
}
inline int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
bitset<5005>f,g[N];
int main(){
	n=read();m=read();
	for(int i = 1;i<=m;i++)a[i]=read(),b[i]=read();
	for(int i = 1;i<=n*2;i++)fa[i]=i,s1[i]=1,s2[i]=0;
	for(int i = m;i>=1;i--){
		int x=find(a[i]),y=find(b[i]);
		if(x==y)continue;
		int w = 0,ggg=(G[a[i]]^G[b[i]]);
		// cerr<<ggg<<endl;
		tot=len=0;
		for(int j = 1;j<=2*n;j++){
			if(fa[j]==j && j!=x && j!=y){
				w+=max(s1[j],s2[j])-min(s1[j],s2[j]);
				p[++tot]=max(s1[j],s2[j])-min(s1[j],s2[j]);
			}
		}
		if(ggg==0){
			w+=max(s1[x]+s2[y],s1[y]+s2[x])-min(s1[x]+s2[y],s1[y]+s2[x]);
			p[++tot]=max(s1[x]+s2[y],s1[y]+s2[x])-min(s1[x]+s2[y],s1[y]+s2[x]);
		}
		else{
			w+=max(s1[x]+s1[y],s2[y]+s2[x])-min(s1[x]+s1[y],s2[y]+s2[x]);
			p[++tot]=max(s1[x]+s1[y],s2[y]+s2[x])-min(s1[x]+s1[y],s2[y]+s2[x]);
		}
		sort(p+1,p+tot+1);
		for(int l = 1,r;l<=tot;l=r+1){
			r=l;
			while(r<=tot&&p[l]==p[r])r++;
			r--;
			int now = r-l+1;
			for(int j = 0;j<=12;j++){
				if(now>=(1<<j))now-=(1<<j),t[++len]=(1<<j)*p[l];
			}
			if(now)t[++len]=now*p[l];
		}
		f.reset();
		f[0]=1;
		for(int j = 1;j<=len;j++)f|=(f<<t[j]);
		// cerr<<"?"<<w<<"??"<<endl;
		if(!(f[w/2] ^ ggg)){
			s1[y]+=s1[x],s2[y]+=s2[x],e[y].push_back({x,0});
			// cerr<<y<<' '<<x<<' '<<0<<endl;
			for(int j = 1;j<=2*n;j++)if(fa[j]==x)fa[j]=y;
		}
		else {
			s1[y]+=s2[x],s2[y]+=s1[x],e[y].push_back({x,1});
			// cerr<<y<<' '<<x<<' ' <<1<<endl;
			for(int j = 1;j<=2*n;j++)if(fa[j]==x)fa[j]=y,G[j]^=1;
		}
	}
	g[0][0]=1;
	int id = 0;
	for(int i = 1;i<=2*n;i++){
		if(fa[i]==i){
			++id;
			g[id]=(g[id]<<s1[i])|(g[id]<<s2[i]);
		}
	}
	int now = n;
	for(int i = 2*n;i>=1;i--){
		if(fa[i]==i){
			if(now-s1[i]>=0&&g[id-1][now-s1[i]]){
				dfs(i);
				now-=s1[i];
			}
			else {
				ans[i]=1;
				now-=s2[i];
				dfs(i);
			}
			--id;
		}
	}
	for(int i = 1;i<=2*n;i++)putchar(ans[i]^48);
	return 0;
}