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
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;

bool checkPattern(unsigned long long number) {
    std::string binaryStr = std::bitset<64>(number).to_string();
    binaryStr.erase(0, binaryStr.find_first_not_of('0'));
    size_t firstOne = binaryStr.find('1');
    size_t lastOne = binaryStr.rfind('1');

    // Check if '1's are found and no '0's are present between the first and last '1'
    if (firstOne != std::string::npos && binaryStr.find('0', firstOne) > lastOne) {
        return true;
    }
    return false;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> edges(m);
    for(auto &[u, v] : edges) cin >> u >> v;
    reverse(edges.begin(), edges.end());
    queue<pair <int, int>> q;
    for(int k = 1; k <= n; k++){
        int s = 0;
        for(int i = 0; i < k; i++)
        {
            s |= 1LL << (63 - i);
        }
        map <int, set <int>> used;
        for(int j = 0; j <= n-k; j++){
            q.push ({s, 0});
            used[s].insert(0);
            s = s >> 1;
        }


        while (!q.empty()) {
            int s = q.front().first;
            //cout << bitset<64>(s) << '\n';
            int sti = q.front().second;
            q.pop();

            for(int i = sti; i < edges.size(); i++)
            {
                int ef = edges[i].first, et = edges[i].second;
                if(used[s].count(sti+1) == 0){
                    used[s].insert(sti+1);
                    q.push({s, sti+1});
                }
                if((s & 1LL << 64 - ef) && not (s & 1LL << 64 - et)){
                    s = s ^ 1LL << 64 - ef;
                    s = s | 1LL << 64 - et;
                   if(used[s].count(sti+1) == 0){
                    used[s].insert(sti+1);
                    q.push({s, sti+1});
                }
                }
            }
        }
        reverse(edges.begin(), edges.end());
        int ans = 0;
        for(auto [xx, x]:used){
            int s = xx;
            for(auto [et, ef]: edges)
            {
                if((s & 1LL << 64 - ef) && not (s & 1LL << 64 - et)){
                        s = s ^ 1LL << 64 - ef;
                        s = s | 1LL << 64 - et;
                    }
            }
            if(checkPattern(s)){
                ans++;
                 //cout << bitset<64>(s) << '\n';
            }
        }
        cout << ans%2 << " ";
        reverse(edges.begin(), edges.end());
    }
    return 0;
}