//by 72
#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define Fd(i, a, b) for(int i = a; i >= b; i --)
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
// #define int long long
using namespace std;

const int mod = 998244353;
const int N = 1e6 + 10;
const int M = 1e4 + 10;
// const int inf = 1e18;
typedef array<int, 3> a3; 
typedef long long ll;

int n, m, f[N], sz1[N], sz2[N], rt[N], qsy[N], f2[N];
pii a[N];
int find(int x) {return x == f[x] ? x : find(f[x]);}
int find2(int x) {return x == f2[x] ? x : f2[x] = find2(f2[x]);}

int v1[N], v2[N];

int s[N], tot = 0; 
// 扩展域并查集
void merge2(int x, int y) {
    int p = find(x), q = find(y);
    if(p == q) return;
    f2[q] = p;
}
bool merge(int x, int y) {
    int p = find(x), q = find(y);
    if(p == q) return false;
    if(sz1[p] + sz2[p] < sz1[q] + sz2[q]) swap(p, q);
    f[q] = p, rt[q] = 0;
    sz1[p] += sz1[q], sz2[p] += sz2[q];
    if(v1[p] && v1[q]) merge2(p, q);
    else if(! v1[p] && v1[q]) v1[p] = v1[q];

    if(v2[p] && v2[q]) merge2(p, q);
    else if(! v2[p] && v2[q]) v2[p] = v2[q];

    s[++ tot] = q;
    return true;
}
void del(){//删除栈顶边
    if(! tot) return;
    int y = s[tot --]; 
    sz1[f[y]] -= sz1[y], sz2[f[y]] -= sz2[y];
    f[y] = y, rt[y] = 1;
}
int cnt[N];

int dp[M][M / 2], pre[M][M / 2];
pii now[N];

void sol() {
    cin >> n >> m;
    // n = 5000, m = 1e6;
    // 再维护一个表示一堆在一个连通块里的
    F(i, 1, 4 * n) {
        f[i] = i, f2[i] = i, rt[i] = 1;
        if(i <= 2 * n) sz1[i] = 1, sz2[i] = 0, v1[i] = i;
        else sz2[i] = 1, sz1[i] = 0, v2[i] = i - 2 * n;
    }
    F(i, 1, m) cin >> a[i].fi >> a[i].se;
    // int now1 = 1, now2 = 2; 
    // F(i, 1, m) {
    //     a[i].fi = now1, a[i].se = now2;
    //     now2 ++;
    //     if(now2 > 2 * n) now1 ++, now2 = now1 + 1;
    // }
    Fd(i, m, 1) {
        auto [u, v] = a[i];
        if(find2(u) == find2(v)) continue;
        if(find(u) == find(v)) continue;
        int sum = 0, qsyy = tot;
        if(! merge(u, v + 2 * n)) continue;
        merge(v, u + 2 * n);
        int mx = 0;
        F(j, 1, 4 * n) if(rt[j]) { 
            // 保证每个连通块会被遍历两次，两次中的集合互为反点
            int x = sz1[j], y = sz2[j];
            if(x > y) swap(x, y);
            mx = max(mx, y - x);
            sum += x, cnt[y - x] ++;
        }
        sum /= 2;
        int idx = 0;
        F(j, 1, mx) if(cnt[j]) now[++ idx] = {j, cnt[j] / 2}, cnt[j] = 0;
        sum = n - sum; // 背出这么多
        bitset<5001> g;
        g[0] = 1;
        F(j, 1, idx) {
            auto [x, y] = now[j];
            if(g[sum]) break;
            for(int j = 0, now; y; j ++) {
                now = min(1 << j, y), y -= now;
                g |= g << (now * x);
            }
        }
        if(! g[sum]) {
            del(), del();
            merge2(u, v);
        }
    }
    vector<a3> tmp;
    F(i, 1, 4 * n) if(rt[i]) {
        tmp.push_back({i, sz1[i], sz2[i]});
        rt[find(i + 2 * n)] = 0; // 保留这个集合 把另一个删了
    }
    dp[0][0] = 1;
    assert(tmp.size() < M);
    for(int i = 0; i < tmp.size(); i ++) {
        auto [id, x, y] = tmp[i];
        F(j, 0, n) if(dp[i][j]) {
            if(j + x <= n) dp[i + 1][j + x] = 1, pre[i + 1][j + x] = j;
            if(j + y <= n) dp[i + 1][j + y] = 1, pre[i + 1][j + y] = j;
        }
    }
    int now = n;
    Fd(i, tmp.size(), 1) {
        auto [id, x, y] = tmp[i - 1];
        int qaq = now - pre[i][now];
        now = pre[i][now];
        if(qaq == y) qsy[id] = 1;
    }
    vector<int> res(2 * n + 1);
    F(i, 1, 4 * n) if(rt[find(i)]) {
        int flag = qsy[find(i)];
        if(i <= 2 * n) res[i] = flag;
        else res[i - 2 * n] = flag ^ 1;
    }
    F(i, 1, 2 * n) cout << res[i]; cout << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int st = clock();
    int t = 1;
    F(i, 1, t) sol();
    // cout << (clock() - st) / 1000.0 << "\n";
    return 0;
}
//sldl