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
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#define ll long long
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n, m;
    cin >> n >> m;
    vector <pair<ll, ll>> ruchy (m);
    for (ll i = 0; i < m; i++){
        cin >> ruchy[i].first >> ruchy[i].second;
        ruchy[i].first--; ruchy[i].second--;
    }

    for (ll k = 1; k <= n; k++){
        ll maska = 0;
        ll akt = 0;
        for (ll i = 0; i < k; i++){
            maska += ((ll)1 << i);
        }
        ll licznik = 0;
        while (maska < ((ll) 1 << n)){
            vector <ll> stany1;
            vector <ll> stany2;
            stany1.push_back(maska);
            for (ll i = m-1; i >= 0; i--){
                ll pom = (m-1)%2;
                if (i % 2 == pom){
                    for (ll j = 0; j < stany1.size(); j++){
                        ll a = stany1[j] & ((ll)1 << ruchy[i].first);
                        ll b = stany1[j] & ((ll)1 << ruchy[i].second);
                        if (a > 0) a = 1;
                        if (b > 0) b = 1;
                        if ((a == 0 && b == 0) || (a == 1 && b == 1)){
                            stany2.push_back(stany1[j]);
                        }else if (a == 0 && b == 1){
                            stany2.push_back(stany1[j]);
                            stany2.push_back(stany1[j] - ((ll)1 << ruchy[i].second) + ((ll)1 << ruchy[i].first));
                        }
                    }
                    stany1.clear();
                }else{
                    for (ll j = 0; j < stany2.size(); j++){
                        ll a = stany2[j] & ((ll)1 << ruchy[i].first);
                        ll b = stany2[j] & ((ll)1 << ruchy[i].second);
                        if (a > 0) a = 1;
                        if (b > 0) b = 1;
                        if ((a == 0 && b == 0) || (a == 1 && b == 1)){
                            stany1.push_back(stany2[j]);
                        }else if (a == 0 && b == 1){
                            stany1.push_back(stany2[j]);
                            stany1.push_back(stany2[j] - ((ll)1 << ruchy[i].second) + ((ll)1 << ruchy[i].first));
                        }
                    }
                    stany2.clear();
                }
            }
            
            if ((m-1) % 2 == 0){
                licznik += stany2.size();
            }else{
                licznik += stany1.size();
            }
            licznik %= 2;

            maska -= ((ll) 1 << akt);
            maska += ((ll) 1 << (akt + k));
            akt++;
        }

        cout << licznik << " ";
    }
    cout << "\n";
}