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

namespace mystd{
class Bitset {
private:
    static constexpr size_t BITS_PER_WORD = 64;
    std::vector<uint64_t> bits;
    size_t numBits;

public:
    // 构造函数
    explicit Bitset(size_t size)
        : bits((size + BITS_PER_WORD - 1) / BITS_PER_WORD, 0), numBits(size) {}

    // 内联函数，访问单个位
    inline bool operator[](size_t index) const {
        size_t wordIndex = index / BITS_PER_WORD;
        size_t bitIndex = index % BITS_PER_WORD;
        return (bits[wordIndex] >> bitIndex) & 1;
    }

    // 内联函数，设置单个位为 1
    inline void set(size_t index) {
        size_t wordIndex = index / BITS_PER_WORD;
        size_t bitIndex = index % BITS_PER_WORD;
        bits[wordIndex] |= (uint64_t(1) << bitIndex);
    }

    // 左移运算符<<=
    Bitset& operator<<=(size_t shift) {
        if (shift == 0 || numBits == 0) {
            return *this;
        }
        if (shift >= numBits) {
            std::fill(bits.begin(), bits.end(), 0);
            return *this;
        }

        size_t wordShift = shift / BITS_PER_WORD;
        size_t bitShift = shift % BITS_PER_WORD;
        size_t n = bits.size();

        if (wordShift > 0) {
            // 使用 memmove 加速内存块移动
            std::memmove(&bits[wordShift], &bits[0], (n - wordShift) * sizeof(uint64_t));
            std::fill(bits.begin(), bits.begin() + wordShift, 0);
        }

        if (bitShift > 0) {
            uint64_t carry = 0;
            for (size_t i = wordShift; i < n; ++i) {
                uint64_t new_carry = bits[i] >> (BITS_PER_WORD - bitShift);
                bits[i] = (bits[i] << bitShift) | carry;
                carry = new_carry;
            }
        }

        // 清除超出 numBits 的位
        size_t excessBits = (BITS_PER_WORD * n) - numBits;
        if (excessBits > 0) {
            bits[n - 1] &= (~uint64_t(0)) >> excessBits;
        }

        return *this;
    }
    Bitset operator<<(size_t shift) const {
        Bitset result(*this);
        result <<= shift;
        return result;
    }

    // 位或赋值运算符|=，使用 SIMD 指令加速
    __attribute__((target("avx2")))
    Bitset& operator|=(const Bitset& other) {
        size_t n = bits.size();
        size_t i = 0;

        // 使用 AVX2 指令一次处理 256 位（4 个 uint64_t）
        for (; i + 4 <= n; i += 4) {
            __m256i a = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(&bits[i]));
            __m256i b = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(&other.bits[i]));
            a = _mm256_or_si256(a, b);
            _mm256_storeu_si256(reinterpret_cast<__m256i*>(&bits[i]), a);
        }

        // 处理剩余的位块
        for (; i < n; ++i) {
            bits[i] |= other.bits[i];
        }
        return *this;
    }

    // 位或运算符|
    Bitset operator|(const Bitset& other) const {
        Bitset result(*this);
        result |= other;
        return result;
    }

    // 打印位集（用于调试）
    void print() const {
        for (size_t i = numBits; i-- > 0;) {
            std::cout << (*this)[i];
            if (i % 8 == 0) {
                std::cout << ' ';
            }
        }
        std::cout << std::endl;
    }
};
}
const int N=5005,M=1000005;
int n,m;
int a[M],b[M];
int fa[N*4];
int siz[N*4];
int num[N*4][2];
int getf(int v)
{
    if(v==fa[v]) return v;
    else return fa[v]=getf(fa[v]);
}
void merge(int u,int v)
{
    int fu=getf(u),fv=getf(v);
    if(fu!=fv)
    {
        num[fu][0]+=num[fv][(fu>n*2)^(fv>n*2)];
        num[fu][1]+=num[fv][(fu>n*2)^(fv>n*2)^1];
        fa[fv]=fu;
    }
    return;
}
vector<pair<int,int>>G[N*2];
int col[N*2];
int cnt[2];
bitset<N>f[N*2];
int tot=0;
int rt[N*2],c[N*2][2];
vector<int>pos;
void dfs(int u,int color)
{
    pos.emplace_back(u);
    col[u]=color;
    cnt[color]++;
    for(auto [v,w]:G[u])
        if(col[v]==-1) dfs(v,color^w);
    return;
}
multiset<int>val;
int sum=0;
void erase(int c0,int c1)
{
    if(c0>c1) swap(c0,c1);
    if(c0==c1) return;
    val.erase(val.lower_bound(c1-c0));
//    val.erase(lower_bound(val.begin(),val.end(),make_pair(c0,c1)));
    sum-=c0;
    return;
}
void insert(int c0,int c1)
{
    if(c0>c1) swap(c0,c1);
    if(c0==c1) return;
    pair<int,int> c=make_pair(c0,c1);
    val.insert(c1-c0);
//    val.insert(lower_bound(val.begin(),val.end(),c),c);
    sum+=c0;
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i]>>b[i];
    for(int i=1;i<=n*4;i++)
        fa[i]=i,num[i][0]=1;
    for(int i=1;i<=n*2;i++)
        val.insert(1);
    for(int i=m;i>=1;i--)
    {
        int u=a[i],v=b[i];
        if(getf(u)==getf(v)||getf(u+n*2)==getf(v+n*2)) continue;
        if(getf(u)==getf(v+n*2)||getf(u+n*2)==getf(v)) continue;
        u=getf(u),v=getf(v);
        int w=1;
        int cu[2]={num[u][0],num[u][1]};
        erase(cu[0],cu[1]);
        int cv[2]={num[v][0],num[v][1]};
        erase(cv[0],cv[1]);
        if(u>n*2) w^=1,u-=n*2;
        if(v>n*2) w^=1,v-=n*2;
        cnt[0]=cu[0]+cv[w],cnt[1]=cu[1]+cv[w^1];
        insert(cnt[0],cnt[1]);
        if(cnt[0]>cnt[1]) swap(cnt[0],cnt[1]);
        bool flag=true;
        if(sum>n)
        {
            flag=false;
        }
        if(flag)
        {
            int ret=n-sum;
            mystd::Bitset f(ret+1);
            f.set(0);
            for(auto c01:val)
            {
                f|=f<<c01;
                if(f[ret]) break;
            }
            if(!f[ret]) flag=false;
        }
        if(!flag)
        {
            erase(cnt[0],cnt[1]);
            cnt[0]=cu[0]+cv[w^1],cnt[1]=cu[1]+cv[w];
            insert(cnt[0],cnt[1]);
            if(w)
            {
                merge(u,v);
                merge(u+n*2,v+n*2);
            }
            else
            {
                merge(u,v+n*2);
                merge(u+n*2,v);
            }
            G[u].emplace_back(v,w^1);
            G[v].emplace_back(u,w^1);
            continue;
        }
        G[u].emplace_back(v,w);
        G[v].emplace_back(u,w);
        if(w)
        {
            merge(u,v+n*2);
            merge(u+n*2,v);
        }
        else
        {
            merge(u,v);
            merge(u+n*2,v+n*2);
        }
    }
    int st=clock();
    fill(col+1,col+n*2+1,-1);
    f[0][0]=1;
    tot=0;
    for(int u=1;u<=n*2;u++)
    {
        if(col[u]==-1)
        {
            cnt[0]=cnt[1]=0;
            dfs(u,0);
            rt[++tot]=u;
            c[tot][0]=cnt[0],c[tot][1]=cnt[1];
            f[tot]=(f[tot-1]<<cnt[0])|(f[tot-1]<<cnt[1]);
        }
    }
    assert(f[tot][n]);
    fill(col+1,col+n*2+1,-1);
    int ret=n;
    for(int i=tot;i>=1;i--)
    {
        int u=rt[i];
        if(ret>=c[i][0]&&f[i-1][ret-c[i][0]])
        {
            ret-=c[i][0];
            dfs(u,0);
        }
        else
        {
            ret-=c[i][1];
            dfs(u,1);
        }
    }
    int ed=clock();
    if((double)(ed-st)/CLOCKS_PER_SEC>0.2) exit(1);
    for(int u=1;u<=n*2;u++)
        cout<<col[u];
    return 0;
}