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
// #include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#include <iostream>
#include <vector>
using namespace std;
bool is_good(uint64_t n) {
    bool ones = false;
    while (n && !(n&1)) {
        n>>=1;        
    }
    while (n && (n&1)) {
        n>>=1;        
    }
    return n==0;
}

int count_onez(uint64_t n) {
    int total=0;
    while (n) {
        if (n&1)
            total++ ;        
        n>>=1;
    }
    return total;
}

bool solve(uint64_t n, vector<pair<int,int>> &ops) {

    for (auto op: ops) {
        if ((n&(1 << (op.first-1))) && !((n&(1 << (op.second-1))))) {
            n &= ~((uint64_t)1 << (op.first-1));
            n |= ((uint64_t)1 << (op.second-1));
        }
    }
    return is_good(n);
}
// TODO:
// check which bites are affected and reuse already calculated values;
int main()
{
    FAST
    int n, m;
    cin >> n >> m;

    uint64_t to = ((uint64_t)1<<(n))-1 ;
    vector<pair<int, int>> commands(m);

    int tmp1, tmp2;
    for (int i = 0 ; i < m ; i++) {
        cin >>  tmp1 >> tmp2;
        commands[i] = {tmp1, tmp2};
    }

    vector<bool> out(n+1);
    int tmp;
    for (int i = 1 ; i <= to; i++) {
        if (solve(i, commands)) {
            tmp = count_onez(i);
            out[tmp] = !out[tmp];
        }
    }
    out.erase(out.begin());
    for (auto v: out){
        if (v) {
            cout << "1 ";
        } else {
            cout << "0 ";
        }
    }
}