// https://www.youtube.com/watch?v=CrymicX875M
// Angel of mercy
// How did you move me
// Why am I on my feet again

#ifndef ONLINE_JUDGE
#include "templates/debug.hpp"
#else
#define debug(...)
#endif

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using u64 = uint64_t;

// #define int i64
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <atcoder/modint>
using namespace atcoder;
using Z1 = modint1000000007;
using Z2 = modint998244353;

constexpr int N = 10000 + 5;
Z1 hash1[N + 1];
Z2 hash2[N + 1];
unordered_set<u64> fails;
int fa[N + 1], sz[N + 1], fad[N + 1], c0[N + 1], c1[N + 1];

int diff_sum = 0;

pair<int, int> find(int x) {
    if (fa[x] == x) return {x, 0};
    auto [f, fv] = find(fa[x]);
    fa[x] = f, fad[x] ^= fv;
    return {f, fad[x]};
}

int dc(int x) {
    if (find(x).first != x) return 0;
    return abs(c0[x] - c1[x]);
}

void merge(int x, int y) {
    x = find(x).first, y = find(y).first;
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    fa[y] = x, sz[x] += sz[y], fad[y] = 1;
    c0[x] += c1[y], c1[x] += c0[y];
}

template <typename Z>
struct Comb {
    std::vector<Z> fact, inv_fact;
    Comb(int n) {
        fact.resize(n + 1, Z(1));
        inv_fact.resize(n + 1, Z(1));
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i;
        }
        inv_fact[n] = Z{1} / fact[n];
        for (int i = n - 1; i >= 0; i--) {
            inv_fact[i] = inv_fact[i + 1] * (i + 1);
        }
    }
    Z get(int n, int m) const {
        if (n < m || m < 0) return 0;
        return fact[n] * inv_fact[m] * inv_fact[n - m];
    }
};

Comb<Z1> comb1(N);
Comb<Z2> comb2(N);

using bs = bitset<N + 1>;
void solve() {
    int n, m; cin >> n >> m;
    n *= 2;
    hash1[0] = 1; hash2[0] = 1;
    for (int i = 1; i <= n; i++) hash1[i] = rng(), hash2[i] = rng();
    Z1 h1 = hash1[1].pow(n); Z2 h2 = hash2[1].pow(n);
    diff_sum = n;
    for (int i = 1; i <= n; i++) {
        fa[i] = i, sz[i] = 1, fad[i] = 0;
        c0[i] = 1, c1[i] = 0;
    }
    vector<Z1> dp1(n + 1);
    vector<Z2> dp2(n + 1);
    for (int i = 0; i <= n; i++) {
        dp1[i] = comb1.get(n, i);
        dp2[i] = comb2.get(n, i);
    }
    auto try_merge = [&](int x, int y, int z) {
        auto nh1 = h1 / hash1[x] / hash1[y] * hash1[z];
        auto nh2 = h2 / hash2[x] / hash2[y] * hash2[z];
        if (fails.contains(u64(nh1.val()) << 32 | nh2.val())) return false;
        // rollback dps
        // for (int i = n; i >= s1; i--) dp1[i] += dp1[i - s1];
        if (x) for (int i = x; i <= n; i++) dp1[i] -= dp1[i - x], dp2[i] -= dp2[i - x];
        if (y) for (int i = y; i <= n; i++) dp1[i] -= dp1[i - y], dp2[i] -= dp2[i - y];
        if (z) for (int i = n; i >= z; i--) dp1[i] += dp1[i - z], dp2[i] += dp2[i - z];
        if (!dp1[diff_sum / 2].val() && !dp2[diff_sum / 2].val()) {
            fails.insert(u64(nh1.val()) << 32 | nh2.val());
            // rollback again
            if (z) for (int i = z; i <= n; i++) dp1[i] -= dp1[i - z], dp2[i] -= dp2[i - z];
            if (x) for (int i = n; i >= x; i--) dp1[i] += dp1[i - x], dp2[i] += dp2[i - x];
            if (y) for (int i = n; i >= y; i--) dp1[i] += dp1[i - y], dp2[i] += dp2[i - y];
            return false;
        }
        h1 = nh1, h2 = nh2;
        return true;
    };

    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        edges[i] = {u, v};
    }
    reverse(edges.begin(), edges.end());
    for (auto [u, v] : edges) {
        u = find(u).first, v = find(v).first;
        if (u == v) continue;
        int diff_add = abs(c0[u] + c1[v] - c0[v] - c1[u]);
        diff_sum += diff_add - dc(u) - dc(v);
        if (diff_sum % 2 == 0 && try_merge(dc(u), dc(v), diff_add)) {
            debug(u, v);
            merge(u, v);
        } else {
            diff_sum -= diff_add - dc(u) - dc(v);
        }
    }

    vector<vector<int>> comp0(n + 1), comp1(n + 1);
    for (int i = 1; i <= n; i++) {
        auto [f, v] = find(i);
        if (v) comp1[f].push_back(i);
        else comp0[f].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        if (c0[i] < c1[i]) swap(comp0[i], comp1[i]), swap(c0[i], c1[i]);
    }
    // run annother dp to get an construction
    vector<bs> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];
        if (dc(i)) {
            dp[i] |= (dp[i - 1] << dc(i));
        }
    }
    if (!dp[n][diff_sum / 2]) {
        cout << "ERROR\n";
        return;
    }
    string ans(n, '0');
    int now = diff_sum / 2;
    for (int i = n; i; i--) {
        if (now >= dc(i) && dp[i - 1][now - dc(i)]) {
            for (int j: comp0[i]) ans[j - 1] = '0';
            for (int j: comp1[i]) ans[j - 1] = '1';
            now -= dc(i);
        } else {
            for (int j: comp0[i]) ans[j - 1] = '1';
            for (int j: comp1[i]) ans[j - 1] = '0';
        }
    }
    cout << ans << '\n';
}
#undef int

// Make bold hypotheses and verify carefully
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

answer.code:19:10: fatal error: atcoder/modint: No such file or directory
   19 | #include <atcoder/modint>
      |          ^~~~~~~~~~~~~~~~
compilation terminated.