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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>


using namespace std;


typedef unsigned long long mask_t;


bool getBit(const mask_t &mask, int b) {
    return mask & (1ULL << b);
}

vector <int> solve(int n, int m, vector <pair<int,int>> &ord) {
    vector <pair<mask_t,mask_t>> pat = {{0ULL, 0ULL}};

    for (auto [a, b]: ord) {
        int numPatterns = pat.size();

        for (int i = 0; i < numPatterns; i++) {
            auto &[maskKnown, maskVal] = pat[i];

            bool aKnown = maskKnown & (1ULL << a);
            bool bKnown = maskKnown & (1ULL << b);

            if (!aKnown && !bKnown) {
                maskKnown ^= (1ULL << a) ^ (1ULL << b);
                pat.push_back({maskKnown, maskVal ^ (1ULL << a) ^ (1ULL << b)});
            } else {
                bool aVal = maskVal & (1ULL << a);
                bool bVal = maskVal & (1ULL << b);

                if (aKnown && bKnown) {
                    if (aVal && !bVal) {
                        maskVal ^= (1ULL << a) ^ (1ULL << b);
                    }
                } else if (aKnown && aVal) {
                    maskKnown ^= (1ULL << a) ^ (1ULL << b);
                    maskVal ^= (1ULL << a) ^ (1ULL << b);
                } else if (bKnown && !bVal) {
                    maskKnown ^= (1ULL << a) ^ (1ULL << b);
                }
            }
        }
    }

    vector <int> ans(n, 0);
    for (auto [maskKnown, maskVal] : pat) {
        if (maskVal == 0ULL) {
            int lastKnown = -1;
            for (int i = 0; i <= n; i++) if (i == n || getBit(maskKnown, i)) {
                int len = i - lastKnown - 1;
                for (int x = len - 1; x >= 0; x -= 2) {
                    ans[x] ^= 1;
                }

                lastKnown = i;
            }
        } else {
            int oneLeft = -1, oneRight = -1;
            for (int i = 0; i < n; i++) if (getBit(maskVal, i)) {
                if (oneLeft == -1) {
                    oneLeft = i;
                }

                oneRight = i;
            }

            bool blocked = false;
            for (int i = oneLeft + 1; i < oneRight; i++) {
                if (getBit(maskKnown, i) && !getBit(maskVal, i)) {
                    blocked = true;
                }
            }

            if (!blocked) {
                int zeroLeft = -1, zeroRight = n;

                for (int i = oneLeft - 1; i >= 0; i--) if (getBit(maskKnown, i)) {
                    zeroLeft = i;
                    break;
                }

                for (int i = oneRight + 1; i < n; i++) if (getBit(maskKnown, i)) {
                    zeroRight = i;
                    break;
                }

                for (int x = zeroLeft + 1; x <= oneLeft; x++) {
                    for (int y = oneRight; y < zeroRight; y++) {
                        ans[y - x] ^= 1;
                    }
                }
            }
        }
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);

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

    vector <pair<int,int>> ord(m);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b; a--; b--;

        ord[i] = {a, b};
    }

    auto ans = solve(n, m, ord);
    for (int x : ans) {
        cout << x << ' ';
    }

    return 0;
}