1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

#define LL long long
#define PL pair<LL, LL>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    int len = 1;
    int l = 1;
    vector<PL> states(1000000);
    vector<int> res(m + 1);

    int a, b;
    while (m--)
    {
        cin >> a >> b;
        for (int k = 0; k < len; ++k)
        {
            auto &[mask, val] = states[k];
            if (mask & val & (1ll << a))
            {
                if (val & (1ll << b)) continue;
                val ^= (1ll << a) | (1ll << b);
                if (mask & (1ll << b)) continue;
                mask ^= (1ll << a) | (1ll << b);
            }
            else if (!(mask & (1ll << a)))
            {
                if (val & (1ll << b)) continue;
                if (mask & (1ll << b)) mask ^= (1ll << a) | (1ll << b);
                else
                {
                    mask |= (1ll << a) | (1ll << b);
                    states[l++] = {mask, val | (1ll << a) | (1ll << b)};
                }
            }
        }
        len = l;
    }

    for (int k = 0; k < len; ++k)
    {
        auto &[mask, val] = states[k];
        if (val)
        {
            int first = 1;
            int last = n;
            while (!(val & (1ll << first))) ++first;
            while (!(val & (1ll << last))) --last;

            bool good = true;
            for (int j = first; j <= last; ++j)
            {
                if ((mask & (1ll << j)) && !(val & (1ll << j)))
                {
                    good = false;
                    break;
                }
            }

            if (!good) continue;

            int block = last - first + 1;

            int left = first;
            int right = last;

            while (left > 1 && !(mask & (1ll << (left - 1)))) --left;
            while (right < n && !(mask & (1ll << (right + 1)))) ++right;

            for (int i = block; i <= n; ++i)
            {
                int farthest = min(first, right - i + 1);
                int closest = max(left, last - i + 1);
                if (closest > farthest) break;
                res[i] ^= (farthest - closest + 1) & 1;
            }
        }
        else
        {
            int block = 0;
            for (int j = 1; j <= n; ++j)
            {
                if (mask & (1ll << j))
                {
                    for (int i = 1; i <= block; ++i) res[i] ^= (block - i + 1) & 1;
                    block = 0;
                }
                else ++block;
            }
            for (int i = 1; i <= block; ++i) res[i] ^= (block - i + 1) & 1;
        }
    }

    for (int i = 1; i <= n; ++i) cout << res[i] << " ";
}