#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5, P = 998244353;
typedef array<int,2> info;
int f[maxn];
info siz[maxn];
#define fp(i, a, b) for (int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = (a), i##_ = (b) - 1; i > i##_; --i)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
using arr = int[maxn];
using ll = int64_t;
/*---------------------------------------------------------------------------*/
class Cipolla {
    int P, I2{};
    using pll = pair<ll, ll>;
#define X first
#define Y second
    ll mul(ll a, ll b) const { return a * b % P; }
    pll mul(pll a, pll b) const { return {(a.X * b.X + I2 * a.Y % P * b.Y) % P, (a.X * b.Y + a.Y * b.X) % P}; }
    template<class T> T POW(T a, int b, T x) { for (; b; b >>= 1, a = mul(a, a)) if (b & 1) x = mul(x, a); return x; }
public:
    Cipolla(int p = 0) : P(p) {}
    pair<int, int> sqrt(int n) {
        int a = rand(), x;
        if (!(n %= P))return {0, 0};
        if (POW(n, (P - 1) >> 1, (int)1) == P - 1) return {-1, -1};
        while (POW(I2 = ((ll) a * a - n + P) % P, (P - 1) >> 1, (int)1) == 1) a = rand();
        x = (int) POW(pll{a, 1}, (P + 1) >> 1, {1, 0}).X;
        if (2 * x > P) x = P - x;
        return {x, P - x};
    }
#undef X
#undef Y
};
/*---------------------------------------------------------------------------*/
#define ADD(a, b) (((a) += (b)) >= P ? (a) -=P : 0) // (a += b) %= P
#define SUB(a, b) (((a) -= (b)) < 0 ? (a) += P: 0)  // ((a -= b) += P) %= P
#define MUL(a, b) ((ll) (a) * (b) % P)
//vector<int> getInv(int L) {
//    vector<int> inv(L); inv[1] = 1;
//    fp(i, 1, L - 1) inv[i] = MUL((P - P / i), inv[P % i]);
//    return inv;
//}
//auto inv = getInv(maxn); // NOLINT
int POW(ll a, int b = P - 2, ll x = 1) { for (; b; b >>= 1, a = a * a % P) if (b & 1) x = x * a % P; return x; }
//int INV(int a) { return a < maxn ? inv[a] : POW(a); }
namespace NTT {
    const int g = 3;
    vector<int> Omega(int L) {
        int wn = POW(g, P / L);
        vector<int> w(L); w[L >> 1] = 1;
        fp(i, L / 2 + 1, L - 1) w[i] = MUL(w[i - 1], wn);
        fd(i, L / 2 - 1, 1) w[i] = w[i << 1];
        return w;
    }
    auto W = Omega(1 << 21); // NOLINT
    void DIF(int *a, int n) {
        for (int k = n >> 1; k; k >>= 1)
            for (int i = 0, y; i < n; i += k << 1)
                fp(j, 0, k - 1)
                    y = a[i + j + k], a[i + j + k] = MUL(a[i + j] - y + P, W[k + j]), ADD(a[i + j], y);
    }
    void IDIT(int *a, int n) {
        for (int k = 1; k < n; k <<= 1)
            for (int i = 0, x, y; i < n; i += k << 1)
                fp(j, 0, k - 1)
                    x = a[i + j], y = MUL(a[i + j + k], W[k + j]),
                    a[i + j + k] = x - y < 0 ? x - y + P : x - y, ADD(a[i + j], y);
        int Inv = P - (P - 1) / n;
        fp(i, 0, n - 1) a[i] = MUL(a[i], Inv);
        reverse(a + 1, a + n);
    }
}
namespace Polynomial {
    using Poly = std::vector<int>;
 
    // mul/div int
    Poly &operator*=(Poly &a, int b) { for (auto &x : a) x = MUL(x, b); return a; }
    Poly operator*(Poly a, int b) { return a *= b; }
    Poly operator*(int a, Poly b) { return b * a; }
    Poly &operator/=(Poly &a, int b) { return a *= POW(b); }
    Poly operator/(Poly a, int b) { return a /= b; }
 
    // Poly add/sub
    Poly &operator+=(Poly &a, Poly b) {
        a.resize(max(a.size(), b.size()));
        fp(i, 0, b.size() - 1) ADD(a[i], b[i]);
        return a;
    }
    Poly operator+(Poly a, Poly b) { return a += b; }
    Poly &operator-=(Poly &a, Poly b) {
        a.resize(max(a.size(), b.size()));
        fp(i, 0, b.size() - 1) SUB(a[i], b[i]);
        return a;
    }
    Poly operator-(Poly a, Poly b) { return a -= b; }
 
    // Poly mul
    void DFT(Poly &a) { NTT::DIF(a.data(), a.size()); }
    void IDFT(Poly &a) { NTT::IDIT(a.data(), a.size()); }
    int norm(int n) { return 1 << (32 - __builtin_clz(n - 1)); }
    void norm(Poly &a) { if (!a.empty()) a.resize(norm(a.size()), 0); }
    Poly &dot(Poly &a, Poly &b) {
        fp(i, 0, a.size() - 1) a[i] = MUL(a[i], b[i]);
        return a;
    }
    Poly operator*(Poly a, Poly b) {
        int n = a.size() + b.size() - 1, L = norm(n);
        if (a.size() <= 8 || b.size() <= 8) {
            Poly c(n);
            fp(i, 0, a.size() - 1) fp(j, 0, b.size() - 1)
                c[i + j] = (c[i + j] + (ll) a[i] * b[j]) % P;
            return c;
        }
        a.resize(L), b.resize(L);
        DFT(a), DFT(b), dot(a, b), IDFT(a);
        return a.resize(n), a;
    }
     
    // Poly inv
    Poly Inv2k(Poly a) { // a.size() = 2^k
        int n = a.size(), m = n >> 1;
        if (n == 1) return {POW(a[0])};
        Poly b = Inv2k(Poly(a.begin(), a.begin() + m)), c = b;
        b.resize(n), DFT(a), DFT(b), dot(a, b), IDFT(a);
        fp(i, 0, n - 1) a[i] = i < m ? 0 : P - a[i];
        DFT(a), dot(a, b), IDFT(a);
        return move(c.begin(), c.end(), a.begin()), a;
    }
    Poly Inv(Poly a) {
        int n = a.size();
        norm(a), a = Inv2k(a);
        return a.resize(n), a;
    }
 
    // Poly div/mod
    Poly operator/(Poly a,Poly b){
        int k = a.size() - b.size() + 1;
        if (k < 0) return {0};
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        b.resize(k), a = a * Inv(b);
        a.resize(k), reverse(a.begin(), a.end());
        return a;
    }
    pair<Poly, Poly> operator%(Poly a, const Poly& b) {
        Poly c = a / b;
        a -= b * c, a.resize(b.size() - 1);
        return {c, a};
    }
     
    // Poly sqrt
    Poly Sqrt(Poly a) {
        int n = a.size(), k = norm(n);
        Poly b = {(new Cipolla(P))->sqrt(a[0]).first}, c;
        a.resize(k * 2, 0);
        for (int L = 2; L <= k; L <<= 1) {
            b.resize(2 * L, 0), c = Poly(a.begin(), a.begin() + L) * Inv(b);
            fp(i, 0, 2 * L - 1) b[i] = MUL(b[i] + c[i], (P + 1) / 2);
        }
        return b.resize(n), b;
    }
     
    // Poly calculus
    void Derivative(Poly &a) {
        fp(i, 1, a.size() - 1) a[i - 1] = MUL(i, a[i]);
        a.pop_back();
    }
}
using namespace Polynomial;
int n,m;
int getf(int x){
    if(x<0)return -getf(-x);
    if(x==f[x])return x;
    else return f[x]=getf(f[x]);
}
multiset<info> s;
bool check()
{
    int siz=s.size();
    vector<Poly> all; 
    for(auto [x,y]:s){
        Poly a(max(x,y)+1);
        a[x]++,a[y]++;
        all.push_back(a);
    }
    for(int j=0;j<15;j++){
        for(int i=0;i+(1<<j)<siz;i+=(1<<(j+1)))all[i]=all[i]*all[i+(1<<j)];
    }
    // cout<<"check = "<<endl;
    // for(auto [x,y]:s)cout<<x<<"/"<<y<<" ";;cout<<endl;
    // cout<<all[0][n]<<endl;
    return all[0][n]>0;
}
bool merge(int x,int y){//如果是x!=y将y取反(x>0 y>0)
    if(getf(x)==-getf(y))return false;
    if(getf(x)==getf(y))return true;
    x=getf(x),y=getf(y);
    if(x<0)x=-x,y=-y;
    if(siz[x][0]+(y>0?siz[y][0]:siz[-y][1])>n)return false;
    if(siz[x][1]+(y>0?siz[y][1]:siz[-y][0])>n)return false;
    // cout<<"merge x="<<x<<" y="<<y<<" s="<<s.size()<<endl;
    {
        s.extract(siz[x]);
        s.extract(siz[abs(y)]);
        if(y>0)siz[y][0]+=siz[x][0],siz[y][1]+=siz[x][1];
        else siz[-y][0]+=siz[x][1],siz[-y][1]+=siz[x][0];
        s.insert(siz[abs(y)]);
        if(check()){
            f[x]=y;return true;
        }
        s.extract(siz[abs(y)]);
        if(y>0)siz[y][0]-=siz[x][0],siz[y][1]-=siz[x][1];
        else siz[-y][0]-=siz[x][1],siz[-y][1]-=siz[x][0];
        s.insert(siz[x]);
        s.insert(siz[abs(y)]);
        return false;
    }    
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n*2;i++)f[i]=i,siz[i][0]=1,s.insert(siz[i]);
    vector<int> ans(n*2+1,0);
    vector<pair<int,int>> q(m);
    for(int i=0;i<m;i++){
        cin>>q[i].first>>q[i].second;
    }
    reverse(q.begin(),q.end());
    string anss;
    for(auto [x,y]:q){
        bool flag=merge(x,-y);

        if(!flag)merge(x,y);
        if(flag)anss.push_back('1');
        else anss.push_back('0');
        // cout<<"x="<<x<<" y="<<y<<" merge="<<flag<<endl;
    }
    // for(int i=1;i<=n;i++)cout<<
    vector<int> vis(n*2+1,0);
    vector<pair<vector<int>,vector<int>>>all;
    vector<vector<int>> dp(n*2+1,vector<int>(n+1));
    dp[0][0]=1;
    int p=0;
    for(int i=1;i<=n*2;i++)if(!vis[i]){
        vector<int> v0,v1;
        v0.push_back(i);
        p++;
        for(int j=i+1;j<=n*2;j++)if(abs(getf(i))==abs(getf(j))){
            if(getf(i)==-getf(j))v1.push_back(j);
            else v0.push_back(j);
            vis[j]=1;
        }
        all.emplace_back(v0,v1);
        for(int j=0;j<=n;j++){
            if(j>=v0.size())dp[p][j]|=dp[p-1][j-v0.size()];
            if(j>=v1.size())dp[p][j]|=dp[p-1][j-v1.size()];
        }
        // cout<<"v0 :";for(auto it:v0)cout<<it<<" ";;cout<<endl;
        // cout<<"v1 :";for(auto it:v1)cout<<it<<" ";;cout<<endl;
    }
    reverse(all.begin(),all.end());
    int now=n;
    // cout<<"???"<<endl;
    for(auto [v0,v1]:all){
        // cout<<"p="<<p<<" now="<<now<<endl;
        if(now>=v0.size()&&dp[p-1][now-v0.size()]){
            for(auto it:v0)ans[it]=0;
            for(auto it:v1)ans[it]=1;
            now-=v0.size();
        }
        else if(now>=v1.size()&&dp[p-1][now-v1.size()]){
            for(auto it:v0)ans[it]=1;
            for(auto it:v1)ans[it]=0;
            now-=v1.size();
        }
        p--;
    }
    assert(p==0&&now==0);
    int cnt[2]={0,0};
    for(int i=1;i<=2*n;i++)cnt[ans[i]]++;
    assert(cnt[0]==cnt[1]);
    // for(int i=1;i<=2*n;i++)cout<<ans[i];;cout<<endl;
    cout<<anss;
}