#include <bits/stdc++.h>

using namespace std;

typedef long long i64;
typedef unsigned long long u64;
typedef double lf;

const int maxn = 10100;

const int mod = 1000855321;
template<typename T>
T add(T x) {
    return x;
}
template<typename T, typename... Ts>
T add(T x, Ts... y) {
    T res = x + add(y...);
    if (res >= mod)
        res -= mod;
    return res;
}
template<typename T, typename... Ts>
T sub(T x, Ts... y) {
    return add(x, mod - add(y...));
}
template<typename T, typename... Ts>
void udd(T &x, Ts... y) {
    x = add(x, y...);
}
template<typename T>
T mul(T x) {
    return x;
}
template<typename T, typename... Ts>
T mul(T x, Ts... y) {
    return (x * 1ll * mul(y...)) % mod;
}
template<typename T, typename... Ts>
void uul(T &x, Ts... y) {
    x = mul(x, y...);
}
int bin(int a, i64 deg) {
    int r = 1;
    while (deg) {
        if (deg & 1)
            uul(r, a);
        deg >>= 1;
        uul(a, a);
    }
    return r;
}
int inv(int x) {
    assert(x);
    return bin(x, mod - 2);
}

int dsu[maxn], rnk[maxn], col[maxn], same_parity[maxn], sz[maxn];
int n;

pair<int, int> find(int x) {
    if (dsu[x] == x) return make_pair(x, 0);
    auto [p, c] = find(dsu[x]);
    c ^= col[x];
    dsu[x] = p;
    col[x] = c;
    return make_pair(p, c);
}

int unite(int x, int y, int c) {
    // assert(x != y);
    // assert(dsu[x] == x && dsu[y] == y);
    if (rnk[x] < rnk[y]) swap(x, y);
    dsu[y] = x;
    col[y] = c;
    rnk[x] += rnk[x] == rnk[y];
    sz[x] += sz[y];
    if (c == 0) {
        same_parity[x] += same_parity[y];
    } else {
        same_parity[x] += sz[y] - same_parity[y];
    }

    same_parity[y] = 0;
    sz[y] = 0;
    return x;
}

typedef vector<int> poly;
poly p;
int deg = 0;

void mul_inplace(poly &p, int a) {
    if (a == 0) {
        return;
    }
    deg += a;
    for (int i = deg; i >= a; --i) {
        udd(p[i], p[i - a]);
    }
}

void div_inplace(poly &p, int a) {
    if (a == 0) {
        return;
    }
    // divide by (1 + x^a)
    for (int i = a; i <= deg; ++i) {
        udd(p[i], mod - p[i - a]);
    }
    deg -= a;
}

void solve() {
    int m;
    cin >> n >> m;
    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].first >> edges[i].second;
        --edges[i].first;
        --edges[i].second;
    }
    reverse(edges.begin(), edges.end());
    for (int i = 0; i < 2 * n; ++i) {
        dsu[i] = i;
        rnk[i] = 0;
        col[i] = 0;
        sz[i] = 1;
        same_parity[i] = 1;
    }
    p.resize(2 * n + 1);
    p[0] = 1;
    for (int i = 0; i < 2 * n; ++i) {
        mul_inplace(p, 1);
    }

    auto try_add_edge = [&](int a, int b, int w) {
        auto [fa, ca] = find(a);
        auto [fb, cb] = find(b);

        if (fa != fb) {
            int bal_a = abs(sz[fa] - 2 * same_parity[fa]);
            int bal_b = abs(sz[fb] - 2 * same_parity[fb]);
            div_inplace(p, bal_a);
            div_inplace(p, bal_b);

            int new_same_parity;
            if ((ca ^ cb) == (w ^ 1)) {
                new_same_parity = same_parity[fa] + (sz[fb] - same_parity[fb]);
            } else {
                new_same_parity = same_parity[fa] + same_parity[fb];
            }
            int new_bal = abs(sz[fa] + sz[fb] - 2 * new_same_parity);

            mul_inplace(p, new_bal);
            // assert(deg % 2 == 0);
            if (p[deg / 2] == 0) {
                div_inplace(p, new_bal);
                mul_inplace(p, bal_a);
                mul_inplace(p, bal_b);
                unite(fa, fb, ca ^ cb ^ w ^ 1);
                return;
            }
            unite(fa, fb, ca ^ cb ^ w);
        }
    };

    for (const auto &[a, b]: edges) {
        try_add_edge(a, b, 1);
    }
    for (int i = 1; i < 2 * n; ++i) {
        try_add_edge(0, i, 0);
        try_add_edge(0, i, 1);
    }

    for (int i = 0; i < 2 * n; ++i) {
        // assert(sz[dsu[i]] == 2 * n);
        auto [ignore, c] = find(i);
        cout << c;
    }
    cout << endl;
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }

    // n = 20;
    // poly p(n + 1);
    // auto print = [&]() {
    //     for (int i = 0; i <= n; ++i) {
    //         cout << p[i] << " ";
    //     }
    //     cout << endl;
    // };
    // p[0] = 1;
    // print();
    // mul_inplace(p, 2);
    // print();
    // mul_inplace(p, 3);
    // print();
    // div_inplace(p, 2);
    // print();
    // div_inplace(p, 3);
    // print();
}