#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)

using namespace std;

const int MOD = 981712597;

int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	if (a < 0)
		a += MOD;
	return a;
}

struct edge{
	int v, u;
};

vector<int> rk, p, clr, siz;

int getp(int a){
	vector<int> path;
	while (a != p[a]){
		path.push_back(a);
		a = p[a];
	}
	reverse(path.begin(), path.end());
	forn(i, int(path.size()) - 1){
		clr[path[i + 1]] ^= clr[path[i]];
		p[path[i]] = a;
	}
	return a;
}

bool check(int a, int b){
	int pa = getp(a), pb = getp(b);
	if (pa != pb) return true;
	return clr[a] != clr[b];
}

void unite(int a, int b){
	int pa = getp(a), pb = getp(b);
	if (pa == pb) return;
	if (rk[pa] < rk[pb]) swap(pa, pb);
	p[pb] = pa;
	rk[pa] += rk[pb];
	clr[pb] = clr[a] ^ clr[b] ^ 1;
	siz[pa] += clr[pb] == 0 ? siz[pb] : rk[pb] - siz[pb];
}

vector<int> dp;

void add(int x){
	if (x == 0) return;
	for (int j = int(dp.size()) - x - 1; j >= 0; --j)
		dp[j + x] = add(dp[j + x], dp[j]);
}

void rem(int x){
	if (x == 0) return;
	forn(j, int(dp.size()) - 1)
		dp[j + x] = add(dp[j + x], -dp[j]);
}

int getx(int sum, int x){
	if (sum < 0) return 0;
	if (sum < x || x == 0) return dp[sum];
	return add(dp[sum], -dp[sum - x]);
}

int getxy(int sum, int x, int y){
	if (sum < 0) return 0;
	if (y == 0) swap(x, y);
	if (y == 0) return dp[sum];
	int cntx = getx(sum, x);
	int cnty = add(cntx, -getx(sum - y, x));
	return cnty;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<edge> e(m);
	forn(i, m){
		cin >> e[i].v >> e[i].u;
		--e[i].v, --e[i].u;
	}
	rk.assign(2 * n, 1);
	p.resize(2 * n);
	iota(p.begin(), p.end(), 0);
	clr.assign(2 * n, 0);
	siz.assign(2 * n, 1);
	
	dp.resize(n + 1);
	dp[0] = 1;
	forn(i, 2 * n) add(1);
	
	int sum = 0;
	int ans = 0;
	for (int i = m - 1; i >= 0; --i){
		int v = e[i].v, u = e[i].u;
		if (!check(v, u)){
			//ans += 2 << i;
			continue;
		}
		int pa = getp(v), pb = getp(u);
		if (pa == pb) continue;
		int mnv = min(siz[pa], rk[pa] - siz[pa]);
		int mnu = min(siz[pb], rk[pb] - siz[pb]);
		int x = rk[pa] - 2 * mnv;
		int y = rk[pb] - 2 * mnu;
		int nsum = sum;
		nsum -= mnv + mnu;
		int one = (clr[v] ^ clr[u] ^ 1) == 0 ? siz[pa] + siz[pb] : siz[pa] + (rk[pb] - siz[pb]);
		one = min(one, rk[pa] + rk[pb] - one);
		nsum += one;
		int xy = (rk[pa] + rk[pb] - one) - one;
		//cerr << "!" << endl;
		//cerr << x << " " << y << " " << xy << " " << nsum << endl;
		//for (int x : dp) cerr << x << " ";
		//cerr << endl;
		//cerr << getxy(n - nsum, x, y) << " " << getxy(n - nsum - xy, x, y) << endl;
		if (getxy(n - nsum, x, y) == 0 && getxy(n - nsum - xy, x, y) == 0){
			//ans += 2 << i;
			continue;
		}
		rem(x); rem(y);
		unite(v, u);
		sum = nsum;
		add(xy);
	}
	
	//cerr << ans << endl;
	vector<int> lst(n + 1);
	dp.assign(n + 1, 0);
	dp[0] = 1;
	sum = 0;
	forn(i, 2 * n) if (i == getp(i)){
		int mn = min(siz[i], rk[i] - siz[i]);
		sum += mn;
		int x = rk[i] - 2 * mn;
		for (int j = n - x; j >= 0; --j) if (dp[j] && !dp[j + x]){
			dp[j + x] = true;
			lst[j + x] = i;
		}
	}
	
	int need = n - sum;
	vector<char> big(2 * n);
	while (need > 0){
		int i = lst[need];
		int mn = min(siz[i], rk[i] - siz[i]);
		int x = rk[i] - 2 * mn;
		big[i] = true;
		need -= x;
	}
	
	vector<vector<vector<int>>> comp(2 * n, vector<vector<int>>(2));
	forn(i, 2 * n){
		int v = getp(i);
		int c = siz[v] < rk[v] - siz[v] ? 0 : 1;
		comp[v][clr[i] ^ c].push_back(i);
	}
	
	string res(2 * n, '0');
	forn(i, 2 * n) if (i == getp(i)){
		for (int v : comp[i][big[i]]){
			res[v] = '1';
		}
	}
	
	cout << res << '\n';
}