#include <iostream>
#include <bitset>

using namespace std;

const int N = 2e4 + 5, M = 1e6 + 5, mod = 998244353;

int n, m, sum, fa[N], sz[N], a[M], b[M], bp[N];

bitset<N> vs[N];

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

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

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

bool iok[N], col[N];

void output()
{
    for (int i = 1; i <= 2 * n; i++)
        if (!iok[i] && find(i) == i)
        {
            int x = find(i <= n ? i + n : i - n);
            iok[x] = 1;
            del(abs(sz[i] - sz[x]));
            if (bp[n/2 - sum])
            {
                if (sz[i] < sz[x])
                    col[i] = 1, col[x] = 0;
                else
                    col[x] = 1, col[i] = 0;
                sum += min(sz[i], sz[x]);
            }
            else
            {
                if (sz[i] > sz[x])
                    col[i] = 1, col[x] = 0;
                else
                    col[x] = 1, col[i] = 0;
                sum += max(sz[i], sz[x]);
            }
        }
    int tt=0;
    for (int i = 1; i <= n; i++)
    tt+=col[find(i)];
    assert(tt==n/2);
    for (int i = 1; i <= n; i++)
    cout<<col[find(i)];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m, n *= 2; bp[0]=1;
    for (int i = 1; i <= m; i++)
        cin >> a[i] >> b[i];
    for (int i = 1; i <= 2 * n; i++)
        fa[i] = i, sz[i] = i <= n;
    for (int i = 1; i <= n; i++)
        add(1);

    for (int i = m; i; i--)
    {
        if (find(a[i]) == find(b[i])) // 不合法
            continue;
        if (find(a[i]) == find(n + b[i])) // 合法，无需操作
            continue;
        int x1 = find(a[i]), x2 = find(n + a[i]), y1 = find(b[i]), y2 = find(n + b[i]);

        //if(vs[x1][y2]||vs[x2][y1]||vs[y1][x2]||vs[y2][x1])continue;//

        sum -= min(sz[x1], sz[x2]) + min(sz[y1], sz[y2]);
        del(abs(sz[x1] - sz[x2])), del(abs(sz[y1] - sz[y2]));
        sum += min(sz[x1] + sz[y2], sz[x2] + sz[y1]);
        add(abs(sz[x1] + sz[y2] - sz[x2] - sz[y1]));
        if ( bp [n/2 - sum] )
        {
            fa[x1] = y2, sz[y2] += sz[x1];
            fa[x2] = y1, sz[y1] += sz[x2];

            vs[y2]|=vs[x1],vs[y1]|=vs[x2];//

            continue;
        }

        vs[x1][y2]=vs[x2][y1]=1;//
        vs[y2][x1]=vs[y1][x2]=1;//

        sum -= min(sz[x1] + sz[y2], sz[x2] + sz[y1]);
        del(abs(sz[x1] + sz[y2] - sz[x2] - sz[y1]));
        sum += min(sz[x1], sz[x2]) + min(sz[y1], sz[y2]);
        add(abs(sz[x1] - sz[x2])), add(abs(sz[y1] - sz[y2]));
    }output();
    return 0;
}

answer.code: In function ‘void output()’:
answer.code:61:5: error: ‘assert’ was not declared in this scope
   61 |     assert(tt==n/2);
      |     ^~~~~~
answer.code:3:1: note: ‘assert’ is defined in header ‘<cassert>’; did you forget to ‘#include <cassert>’?
    2 | #include <bitset>
  +++ |+#include <cassert>
    3 |