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

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

void input() {
    std::cin >> n >> m;
    int x, y;
    for (int i = 0; i < m; i++) {
        std::cin >> x >> y;
        orders.push_back(std::make_pair(x - 1, y - 1));
    }
}

int read(int x, int pos) {
    return x & (1 << pos);
}

int set(int x, int pos, int v) {
    if (v == 0) {
        return x & ~(1 << pos);
    }
    return x | (1 << pos);
}

int execute(int x, int s) {
    if (read(x, orders[s].first) && !read(x, orders[s].second)) {
        x = set(x, orders[s].first, 0);
        x = set(x, orders[s].second, 1);
    }

    return x;
}

bool check(int x) {
    bool started = false;
    bool finished = false;
    for (int i = 0; i < n; i++) {
        if (!started && read(x, i)) {
            started = true;
        }

        if (started && !read(x, i)) {
            finished = true;
        }

        if (finished && read(x, i)) {
            return false;
        }
    }
    return true;
}

void solve() {
    int result[n];
    for (int i = 0; i < n; i++) {
        result[i] = 0;
    }

    for (int x = 1; x < (1 << n); x++) {
        int v = x;
        for (int s = 0; s < m; s++) {
            v = execute(v, s);
        }
        if (!check(v)) {
            continue;
        }
        int ones = 0;
        for (int i = 0; i < n; i++) {
            if (read(x, i)) {
                ones++;
            }
        }
        result[ones - 1]++;
    }

    for (int i = 0; i < n; i++) {
        std::cout << result[i] % 2 << " ";
    }
    std::cout << "\n";
}

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

    input();
    solve();

    return 0;
}