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
/**
 * Patryk Kisielewski
 * 
 * Potyczki Algorytmiczne 2024
 * Zadanie: DES - Desant 3 [B]
*/
#include <set>
#include <vector>
#include <utility>
#include <cstdio>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <bitset>

using namespace std;

long long masks[] = {
    0, 2, 6, 14, 30, 62, 126, 254, 510, 1022, 2046, 4094, 8190, 16382, 32766, 65534, 131070, 262142, 524286, 1048574,
    2097150, 4194302, 8388606, 16777214, 33554430, 67108862, 134217726, 268435454, 536870910, 1073741822, 2147483646,
    4294967294, 8589934590, 17179869182, 34359738366, 68719476734, 137438953470, 274877906942, 549755813886,
    1099511627774, 2199023255550
};

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;

    cin >> n >> m;

    vector<pair<long, long>> moves(m);

    int a, b;

    for (int i = m - 1; i >= 0; --i) {
        cin >> a >> b;
        moves[i].first = (1LL << a);
        moves[i].second = (1LL << b);
    }

    cout << (n % 2) << ' ';

    for (int k = 2; k < n; ++k) {
        long long mask = masks[k];
        int nk = n - k + 1;
        set<long long> combinations;
        for (int i = 0; i < nk; ++i) {
            combinations.insert(mask << i);
        }
        for (auto& move : moves) {
            set<long long> current = combinations;
            for (auto& combination : current) {
                if (combination & move.first) {
                    if (!(combination & move.second)) {
                        if (current.find((combination ^ move.first) | move.second) == current.end()) {
                            combinations.erase(combination);
                        }
                    }
                } else if (combination & move.second) {
                    combinations.insert((combination ^ move.second) | move.first);
                }
            }
        }

        cout << (combinations.size() % 2) << ' ';
    }
    cout << "1 " << endl;

    return 0;
}