//O
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10, M = 2e6 + 10;
int n, m, a[M], b[M], col[N], fa[N];
int sx[N], sy[N];
typedef long long ll;
const ll P = 998244853, Q = 1e9 + 9;
ll f[N], g[N];
ll ff[N], gg[N];

int bs = 0;
void del(int x){
    // printf("del %d\n", x);
    if(!x) return;
    for(int i = x; i <= n+n; ++ i){
        f[i] = (f[i] + P - f[i-x]) % P;
        ff[i] = (ff[i] + Q - ff[i-x]) % Q;
    }
}
void ins(int x){
    // printf("ins %d\n", x);
    if(!x) return;
    for(int i = n+n; i >= x; -- i){
        f[i] = (f[i] + f[i-x]) % P;
        ff[i] = (ff[i] + ff[i-x]) % Q;
    }
}
bool chk(){
    // printf("chk %d %d\n", bs, f[n-bs]);
    return f[n-bs] || ff[n-bs];
}

void mg(int pp, int qq){
    // printf("%d %d\n", pp, qq);
    int x = pp, y = qq;
    if(fa[x] == fa[y]){
        return;
    }
    int xx = fa[x];
    int yy = fa[y];
    memcpy(g, f, sizeof(g));
    memcpy(gg, ff, sizeof(gg));
    int tt = bs;
    del(abs(sx[xx] - sy[xx]));
    bs -= min(sx[xx], sy[xx]);
    del(abs(sx[yy] - sy[yy]));
    bs -= min(sx[yy], sy[yy]);
    if(col[x] == col[y]){
        ins(abs(sx[xx]+sy[yy] - sx[yy]-sy[xx]));
        bs += min(sx[xx]+sy[yy], sx[yy]+sy[xx]);
    } else {
        ins(abs(sx[xx]+sx[yy] - sy[xx]-sy[yy]));
        bs += min(sx[xx]+sx[yy], sy[xx]+sy[yy]);
    }
    if(chk()){
        // puts("ok");
        if(col[x] == col[y]){
            sx[xx] += sy[yy];
            sy[xx] += sx[yy];
        } else {
            sx[xx] += sx[yy];
            sy[xx] += sy[yy];
        }
        sx[yy] = sy[yy] = 0;
        bool op = (col[x] == col[y]);
        for(int j = 1; j <= n+n; ++ j){
            if(fa[j] == yy){
                fa[j] = xx;
                if(op){
                    col[j] ^= 1;
                }
            }
        }
    } else {
        memcpy(f, g, sizeof(g));
        memcpy(ff, gg, sizeof(gg));
        bs = tt;
    }
}

int main(){
    // srand(time(0));
    scanf("%d%d", &n, &m);
    a[0] = 1, b[0] = 2;
    for(int i = 1; i <= m; ++ i){
        scanf("%d%d", &a[i], &b[i]);
        // a[i] = 1;
        // b[i] = n+n-i+1;
        // a[i] = rand() % (n+n) + 1;
        // b[i] = rand() % (n+n) + 1;
        // printf("%d %d\n", a[i], b[i]);
    }
    f[0] = ff[0] = 1;
    for(int i = 1; i <= n + n; ++ i){
        fa[i] = i;
        sx[i] = 1;
        ins(1);
    }
    for(int i = m; i >= 0; -- i){
        mg(a[i], b[i]);
    }
    int px = 0, py = 0, cl = 0;
    for(int i = 1; i <= n+n; ++ i){
        if(sx[i] && sy[i]){
            cl = i;
            break;
        }
    }
    for(int i = 1; i <= n+n; ++ i){
        if(fa[i] == cl && col[i] == 0) px = i;
        if(fa[i] == cl && col[i] == 1) py = i;
    }
    // printf("%d %d\n", px, py);
    for(int i = 2; i <= n+n; ++ i){
        if(fa[i] != fa[px]){
            mg(px, i);
        }
        if(fa[i] != fa[py]){
            mg(py, i);
        }
        if(fa[i] != fa[px]){
            // puts("123");
            for(int j = 1; j <= n+n; ++ j){
                if(fa[j] == fa[i]){
                    col[j] ^= 1;
                }
            }
            swap(sx[fa[i]], sy[fa[i]]);
            mg(px, i);
        }
        if(fa[i] != fa[py]){
            // puts("123");
            for(int j = 1; j <= n+n; ++ j){
                if(fa[j] == fa[i]){
                    col[j] ^= 1;
                }
            }
            swap(sx[fa[i]], sy[fa[i]]);
            mg(py, i);
        }
    }
    for(int i = 1; i <= n+n; ++ i){
        if(fa[i] == i){
            printf("%d %d\n", sx[i], sy[i]);
        }
    }
    for(int i = 1; i <= n+n; ++ i){
        putchar(col[i]+'0');
    }
    puts("");
    // for(int i = m; i >= 1; -- i){
    //     putchar((col[a[i]]==col[b[i]])+'0');
    // }
    return 0;
}