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 <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int,int>> v;

set<long long> wybr;

bool getBit(long long l, int b) { return ((l & (1<<b)) >> b); }

void dzial(long long cur, int ruch) {
    if(ruch >= m) {
        wybr.insert(cur);
        return;
    }

    pair<int,int> r = v[m-ruch-1];
    bool ba = getBit(cur,r.first), bb = getBit(cur,r.second);
    if( ba && !bb) return; //zle

    dzial(cur, ruch+1);
    if(ba == bb) return; //nie wystapil ruch

    cur = cur | (1<<r.first);
    cur = cur ^ (1<<r.second);
    dzial(cur, ruch+1);
}

int ileDla(int x) {
    wybr = set<long long>();
    if(x==1) return n;
    if(x==n) return 1;

    long long cur = (1<<x)-1;

    dzial(cur,0);
    for (int i = x; i < n; ++i) {
        cur = cur | (1<<i);
        cur = cur ^ (1<<(i-x));
        dzial(cur,0);
    }

    return wybr.size();
}

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

    v = vector<pair<int,int>>(m);

    int a,b;
    for(int i=0;i<m;i++){
        cin >> a >> b;
        v[i] = {a-1,b-1};
    }

    for (int i = 1; i <= n; ++i) {
        int w = ileDla(i);
        cout<<(w%2)<<" ";
    }

    //int w = ileDla(3);

}

/*
 10 4
 4 1
 1 2
 3 4
 1 4

 4 4
 4 1
 1 2
 3 4
 1 4
 */