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
#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

int n, m;
vector<pair<int, int>> orders;

bool getBit(long long conf, int position) {
    return (conf >> position) & 1;
}

void onBit(long long &conf, int position) {
    conf |= (1LL << position);
}

void swap(long long &conf, int position1, int position2) {
    conf ^= (1LL << position1) | (1LL << position2);
}

int orderFirst(int i) {
    return orders[m - i - 1].first - 1;
}

int orderSecond(int i) {
    return orders[m - i - 1].second - 1;
}

bool solveConf(long long conf) {
    int i = 0;
    bool result = false;
    bool forward = true;
    while (true) {
        if (i == m) {
            result = !result;
            forward = false;
            i--;
        } else if (forward) {
            if (getBit(conf, orderFirst(i)) && !getBit(conf, orderSecond(i))) {
                forward = false;
                i--;
            } else {
                i++;
            }
        } else if (i < 0) {
            return result;
        } else {
            bool bitFirst = getBit(conf, orderFirst(i));
            bool bitSecond = getBit(conf, orderSecond(i));
            if (!bitFirst && bitSecond) {
                swap(conf, orderFirst(i), orderSecond(i));
                forward = true;
                i++;
            } else if (bitFirst && !bitSecond) {
                swap(conf, orderFirst(i), orderSecond(i));
                i--;
            } else {
                i--;
            }
        }
    }
}

bool solve(int k) {
    bool result = false;
    for (int i = 0; i < n - k + 1; i++) {
        long long conf = 0LL;
        for (int j = i; j < i + k; j++) {
            onBit(conf, j);
        }
        result = result != solveConf(conf);
    }
    return result;
}

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

    cin >> n >> m;

    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        orders.push_back({a, b});
    }

    cout << n % 2 << " ";
    for (int k = 2; k < n; k++) {
        cout << (solve(k) ? "1 " : "0 ");
    }
    cout << 1 << " " << endl; // TODO remove " "
}