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
#include <cstdio>
#include <vector>
#include <algorithm>

typedef unsigned long long int ULONG;

void set(ULONG &state, ULONG p) {
    state |= (1LL<<p);
}

void unset(ULONG &state, ULONG p) {
    state &= (~(1LL<<p));
}

unsigned get(ULONG state, ULONG p) {
    return (state & (1LL<<p)) > 0;
}

std::vector<ULONG> solve(ULONG s, const std::vector<std::pair<int, int> > &orders) {
    std::vector<ULONG> states = {s};

    for (auto &order : orders) {
        std::vector<ULONG> nstates;
        int a = order.first-1;
        int b = order.second-1;

        for (auto &state : states) {
            if (get(state, a) == 0 && get(state, b) == 1) {
                ULONG ns = state;
                set(ns, a);
                unset(ns, b);
                nstates.push_back(ns);
                nstates.push_back(state);
            } else if (get(state, a) == 0 || get(state, b) == 1) {
                nstates.push_back(state);
            }   
        }

        std::sort(nstates.begin(), nstates.end());
        nstates.erase( std::unique(nstates.begin(), nstates.end() ), nstates.end() );
        states = std::move(nstates);
    }

    return states;
}

int main() {
    int N,M;
    std::vector<std::pair<int, int> > orders;

    scanf("%d %d", &N, &M);
    for (int i=0; i<M; ++i) {
        int a,b;
        scanf("%d %d", &a, &b);
        orders.emplace_back(a,b);
    }
    std::reverse(orders.begin(), orders.end());

    for (int k=1; k<=N; ++k) {
        std::vector<ULONG> result;

        for (int spos=0; spos+k<=N; ++spos) {
            ULONG state = 0;

            for (int p=spos; p-spos<k; ++p) {
                set(state, p);
            }

            auto tmp = solve(state, orders);
            result.insert(result.end(), tmp.begin(), tmp.end());
        }

        std::sort(result.begin(), result.end() );
        result.erase( std::unique(result.begin(), result.end() ), result.end() );
        printf("%d ", (int)(result.size() % 2));
    }

    return 0;
}