#include<bits/stdc++.h>
using namespace std;
#define V vector
#define all1(x) (x).begin() + 1, (x).end()
#define all0(x) (x).begin(), (x).end()
#define pb push_back
typedef long long LL;
typedef pair<int, int> pi;
#define fi first
#define se second
#define cout std::cout
LL INFLL = 8e18 + 10;
const int INF = 2e9 + 100;

const LL mod = 444445555566666677;
LL MOD(LL x) {
    if(x >= mod) return x - mod;
    if(x < 0) return x + mod;
    return x;
}

const int MN = 1e4 + 10;
int f[MN], siz[MN], dis[MN], same[MN];

int par(int x) {
    if(x == f[x]) return x;
    int p = par(f[x]);
    dis[x] ^= dis[f[x]];
    f[x] = p;
    return p;
}

int get_d(int x) {
    x = par(x);
    return abs(siz[x] - same[x] * 2);
}

int cal_n_same(int a, int b, int cur_dis) {
    int pa = par(a), pb = par(b);
    assert(pa != pb);
    int d = dis[a] ^ dis[b] ^ cur_dis;
    if(d) {
        return same[pb] + siz[pa] - same[pa];
    } return same[pb] + same[pa];
}

int cal_n_d(int a, int b, int cur_dis) {
    int pa = par(a), pb = par(b);
    assert(pa != pb);
    int n_same = cal_n_same(a, b, cur_dis);
    return abs(siz[pa] + siz[pb] - n_same * 2);
}

void mer(int a, int b, int cur_dis) {
    // cout << "mer : " << a << " " << b << " " << cur_dis << endl;
    int pa = par(a), pb = par(b);
    assert(pa != pb);
    same[pb] = cal_n_same(a, b, cur_dis);
    dis[pa] = dis[a] ^ dis[b] ^ cur_dis;
    f[pa] = pb;
    siz[pb] += siz[pa];
}

void ini(int n) {
    for(int i = 1; i <= n; i++) f[i] = i, siz[i] = 1, same[i] = 1;
}

int main() {
    int n; cin >> n;
    ini(n * 2);
    int minus = 0;
    V<LL> backpack(4 * n + 1);
    backpack[0] = 1;
    auto add = [&](int x) -> void {
        if(x == 0) return;
        // cout << "x : " << x << endl;
        minus += x;
        x *= 2;
        for(int i = 4 * n; i >= 0; i--) {
            if(i - x >= 0) backpack[i] = MOD(backpack[i] + backpack[i - x]);
        }
    };
    auto del = [&](int x) -> void {
        if(x == 0) return;
        minus -= x;
        x *= 2;
        for(int i = 0; i <= n * 4; i++) {
            if(i - x >= 0) backpack[i] = MOD(backpack[i] - backpack[i - x]);
        }
    };

    auto ok = [&]() -> bool {
        return backpack[minus];
    };

    int m; cin >> m;
    V<pi> ask(m + 1);
    for(int i = 1; i <= m; i++) cin >> ask[i].fi >> ask[i].se;
    reverse(all1(ask));

    ask.resize(m + 2 * n);
    for(int i = 1; i < 2 * n; i++) ask.pb({i, i + 1});
    m = m + 2 * n - 1;

    string ans;

    for(int i = 1; i <= 2 * n; i++) {
        add(get_d(i));
    }

    assert(ok());

    auto show_backpack = [&]() -> void {
        cout << "show_bcakpack" << endl;
        for(int i = 0; i <= 4 * n; i++) cout << backpack[i] << " ";
        cout << "minus : " << minus << endl;
    };

    for(int i = 1; i <= m; i++) {
        auto [x, y] = ask[i];
        // cout << "i : " << i << endl;
        // cout << "x, y: " << x << " " << y << endl;
        // show_backpack();
        if(par(x) != par(y)) {
            // cout << "not same pile" << endl;
            int n_d = cal_n_d(x, y, 1);
            int n_op_d = cal_n_d(x, y, 0);
            int dx = get_d(x), dy = get_d(y);

            del(dx);
            del(dy);
            add(n_d);
            if(ok()) {
                mer(x, y, 1);
                assert(get_d(x) == n_d);
            }
            else {
                del(n_d);
                add(n_op_d);
                assert(ok());
                mer(x, y, 0);
                assert(get_d(x) == n_op_d);
            }
        }
    }

    for(int i = 1; i <= 2 * n; i++) {
        par(i);
        cout << dis[i];
    }
    cout << endl;
}