#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
#include<ranges>
#include<array>
#include<stdint.h>
using namespace std;
using LL = long long;

template<const int T>
struct ModInt {
    const static int mod = T;
    int x;
    ModInt(int x = 0) : x(x % mod) {}
    ModInt(long long x) : x(int(x % mod)) {} 
    int val() { return x; }
    ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
    ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
    bool operator == (const ModInt &a) const { return x == a.x; };
    bool operator != (const ModInt &a) const { return x != a.x; };
    void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }
    void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }
    void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }
    void operator /= (const ModInt &a) { *this = *this / a; }
    friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod);}
    friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a;}
    friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}
    friend istream &operator>>(istream &is, ModInt &t){return is >> t.x;}

    ModInt pow(int64_t n) const {
        ModInt res(1), mul(x);
        while(n){
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    
    ModInt inv() const {
        int a = x, b = mod, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        if (u < 0) u += mod;
        return u;
    }
    
};
using mint1 = ModInt<1000000007>;
using mint2 = ModInt<998244353>;

const int maxn = 2e4 + 5;
int p[maxn], sz1[maxn], sz2[maxn];
int cnt[maxn];

int find(int x){
    return p[x] == x ? x : p[x] = find(p[x]);
}

void merge(int x, int y){
    x = find(x), y = find(y);
    if (x != y){
        p[x] = y;
        sz1[y] += sz1[x];
        sz2[y] += sz2[x];
    }
}

template<typename T>
struct Bag{
    
    vector<T> dp;
    int n;

    Bag(int _n = 0){
        n = _n;
        dp.resize(n + 1);
        dp[0] = 1;
    }

    void add(int x){
        if (x == 0) return;
        for(int i = n; i >= x; i--){
            dp[i] += dp[i - x];
        }
    }

    void del(int x){
        if (x == 0) return;
        for(int i = x; i <= n; i++){
            dp[i] -= dp[i - x];
        }
    }

};

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;
    n *= 2;
    vector<pair<int, int> > edge(m);
    for(auto &[x, y] : edge){
        cin >> x >> y;
    }
    for(int i = 1; i <= n; i++){
        p[i] = i;
        p[i + n] = i + n;
        sz1[i] = 1;
        sz2[i + n] = 1;
    }

    Bag<mint1> b1(n / 2);
    Bag<mint2> b2(n / 2);
    int sum = 0;
    for(int i = 1; i <= n; i++) b1.add(1), b2.add(1);

    for(auto [x, y] : edge | views::reverse){
        if (find(x) == find(y) or find(x) == find(y + n)) continue;
        int s1 = sz1[find(x)], s2 = sz2[find(x)];
        if (s1 > s2) swap(s1, s2);
        int s3 = sz1[find(y)], s4 = sz2[find(y)];
        if (s3 > s4) swap(s3, s4);

        int s5 = sz1[find(x)] + sz2[find(y)];
        int s6 = sz2[find(x)] + sz1[find(y)];
        if (s5 > s6) swap(s5, s6);

        auto bk1 = b1;
        auto bk2 = b2;
        auto bksum = sum;

        sum -= s1;
        sum -= s3;
        sum += s5;
        b1.del(s2 - s1);
        b1.del(s4 - s3);
        b2.del(s2 - s1);
        b2.del(s4 - s3);
        b1.add(s6 - s5);
        b2.add(s6 - s5);
        if (b1.dp[n / 2 - sum].val() and b2.dp[n / 2 - sum].val()){
            merge(x, y + n);
            merge(x + n, y);
        }
        else{
            b1.del(s6 - s5);
            b2.del(s6 - s5);
            sum -= s5;
            int s7 = s1 + s3, s8 = s2 + s4;
            b1.add(s7);
            b2.add(s8);
            sum += s7;
            merge(x, y);
            merge(x + n, y + n);
        }
    }

    vector<vector<int> > pos(2 * n + 1);
    for(int i = 1; i <= n; i++){
        pos[find(i)].push_back(i);
    }

    auto get = [&](int x){
        return x <= n ? x : x - n;
    };

    vector<bool> v(n + 1);
    vector<pair<vector<int>, vector<int> > > p;
    for(int i = 1; i <= 2 * n; i++){
        if (!pos[i].empty()){
            if (v[get(pos[i][0])]) continue;
            p.push_back({});
            for(auto x : pos[i]){
                v[get(x)] = true;
                if (x <= n) p.back().first.push_back(x);
                else p.back().second.push_back(x - n);
            }
        }
    }
    const int s = p.size();
    vector<vector<int> > f(s + 1, vector<int>(n / 2 + 1));
    vector<vector<int> > pre(s + 1, vector<int>(n / 2 + 1));
    f[0][0] = 1;
    for(int i = 0; i < s; i++){
        auto &[v1, v2] = p[i];
        for(int j = 0; j + v1.size() <= n / 2; j++){
            if (f[i][j]){
                f[i + 1][j + v1.size()] = 1;
                pre[i + 1][j + v1.size()] = 0;
            }
        }
        for(int j = 0; j + v2.size() <= n / 2; j++){
            if (f[i][j]){
                f[i + 1][j + v2.size()] = 1;
                pre[i + 1][j + v2.size()] = 1;
            }
        }
    }
    vector<int> ans(n + 1);
    for(int i = s - 1, j = n / 2; i >= 0; i--){
        auto &[v1, v2] = p[i];
        if (pre[i + 1][j] == 0){
            j -= v1.size();
            for(auto x : v1) ans[x] = 1;
        }
        else{
            j -= v2.size();
            for(auto x : v2) ans[x] = 1;
        }
    }
    for(int i = 1; i <= n; i++) cout << ans[i];
    cout << '\n';

}