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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (b); i >= (a); i--)
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
auto &operator<<(auto &o, pair<auto, auto> p) {
    return o << "(" << p.st << ", " << p.nd << ")";
}
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
    o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
    return o << "}";
}
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { ((cerr<<$<<"; "),...) << endl; }(x)

const int nax = 1005;
int from[nax];
int to[nax];
int n, m;
vector<int> cnt, cnt2;
ll ans[nax];

void brucik(){
    cnt.resize(1 << n, 0); cnt2 = cnt;
    rep(i, 1, (1 << n) - 1) cnt[i] = 1;
    rep(r, 1, m){
        int x = from[r] - 1;
        int y = to[r] - 1;
        rep(mask, 0, (1 << n) - 1) cnt2[mask] = 0;
        rep(mask, 0, (1 << n) - 1){
            if((mask & (1 << x)) && (!(mask & (1 << y)))){
                cnt2[mask ^ (1 << x) ^ (1 << y)] += cnt[mask];
            }
            else cnt2[mask] += cnt[mask];
        }
        swap(cnt, cnt2);
    }

    rep(i, 1, n){
        rep(j, i, n){
            int mask = 0;
            rep(k, i, j) mask ^= (1 << (k - 1));
            ans[j - i + 1] += cnt[mask];
        }
    }
    rep(i, 1, n) cout << ans[i] % 2 << " ";
    cout << "\n";
    exit(0);
}

bitset<40> emp;

void go(vector<bitset<40>> jazda){    
    vector<bitset<40>> alive, nxt;
    alive = jazda;
    nxt.clear();
    per(i, 1, m){
        int x = from[i];
        int y = to[i];
        for(auto cur : alive){
            if(cur[x] == 0 && cur[y] == 1){
                nxt.pb(cur);
                auto cp = cur;
                cp[x] = 1;
                cp[y] = 0;
                nxt.pb(cp);
            }
            else if(cur[x] == 1 && cur[y] == 0){
                continue;
            }
            else{
                nxt.pb(cur);
            }
        }
        swap(alive, nxt);
        nxt.clear();
    }
    ans[jazda[0].count()] += SZ(alive);
}

void solve(){
    cin >> n >> m;
    rep(i, 1, m) cin >> from[i] >> to[i];
    if((1LL << n) * m <= 1024LL * 1024 * 1000){
        brucik();
    }

    emp.reset();
    rep(len, 1, n){
        vector<bitset<40>> jazda;
        rep(i, 1, n - len + 1){
            auto akt = emp;
            rep(j, i, i + len - 1) akt[j] = true;
            jazda.pb(akt);
        }
        go(jazda);
    }
    rep(i, 1, n) cout << ans[i] % 2 << " ";
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    // cin >> tt;
    rep(te, 1, tt) solve();
    return 0;
}