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
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
// Author   : Jakub Rożek
// Task     : Desant 3
// Contest  : PA 2024 r4 B
// Memory   : O(2^(n/2))
// Time     : O(2^(n/2) * (m + n^2))
// Solution : Symuluje sprytnie wszystkie kombinacje

#include "bits/stdc++.h"
using namespace std;
using LL = long long;
template <typename T>
using P = pair<T, T>;
template <typename T>
using VV = vector<vector<T>>;
#define all(x) x.begin(), x.end()
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i,n) for(int i=0; i<(n); ++i)
#define ssize(x) int((x).size())
#ifdef DEBUG
template <typename T1, typename T2>
auto&operator<<(auto&o,pair<T1,T2>p){return o<<'('<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";for(auto e:x)o<<","<<e;return o<<"}";}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(x)
#else
#define debug(...) {}
#endif

// const int INF = 1'000'000'009;
const int mod = 2;
const int N = 35;
// const int M = 1'000;

int n, m, p, xx, yy;
LL odp[N+1];
LL pref[3][N+1];
LL w1, w2, x, y, z;
vector <P<LL>> zbior[2]; 

void solution() {
    cin >> n >> m;

    p = 0;
    zbior[p].emplace_back(0LL, 0LL);

    REP (i, m) {
        cin >> xx >> yy;
        x = 1LL << xx;
        y = 1LL << yy;
        z = x | y;
        for (auto w: zbior[p]) {
            w1 = w.first;
            w2 = w.second;
            if ((w1 & z) == 0LL) {
                w1 |= z;
                zbior[1-p].emplace_back(w1, w2);
                w2 |= z;
            } else if (((w2&x)&w1) || (((~w2)&y)&w1)) {
                if (bool(w1&x) != bool(w1&y)) w1 ^= z;
                if (bool(w2&x) != bool(w2&y)) w2 ^= z;
            }
            zbior[1-p].emplace_back(w1, w2);
        }
        zbior[p].clear();
        p = 1-p;
    }
    
    pref[0][0] = 0;
    pref[1][0] = 0;
    pref[2][0] = 0;
    for (auto w: zbior[p]) {
        w1 = w.first;
        w2 = w.second;
        FOR (i, 1, n) {
            x = 1LL << i;
            pref[0][i] = pref[0][i-1];
            pref[1][i] = pref[1][i-1];
            pref[2][i] = pref[2][i-1];
            if ((w1&x) == 0LL) pref[2][i] += 1;
            else if ((w2&x) == 0LL) pref[0][i] += 1;
            else pref[1][i] += 1;
        }
 
        FOR (i, 1, n) {
            FOR (j, i, n) {
                if (pref[0][j]-pref[0][i-1] > 0) continue;
                if (pref[1][j]-pref[1][i-1] < pref[1][n]) continue;
                odp[j-i+1]++;
            }
        }
    }

    FOR (i, 1, n) cout << odp[i] % mod << ' ';
    cout << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tests = 1;
    // cin>>tests;
    FOR (i, 1, tests) {
        solution();
    }
    return 0;
}