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
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;

#define loop(i, a, b) for(ll i = a; i <= b; i++)
#define loop_rev(i, a, b) for(ll i = a; i >= b; i--)
using ll = int64_t;

constexpr int MAX_N = 35 + 1;
constexpr int MAX_M = 1000 + 1;
#define DEBUG constexpr(0)
#define DEBUG_IDS constexpr(0)

int n, m;
struct Edge { int a, b; };

int res[MAX_N];
Edge edges[MAX_M];

int is_cool(ll mask) {
  static int arr[MAX_N] = {};

  loop(curr, 1, n) {
    arr[curr] = !!(mask & (1 << (curr - 1)));
  }

  loop(i, 0, m-1) {
    auto [ a, b ] = edges[i];
    if(arr[a] && !arr[b]) swap(arr[a], arr[b]);
  }

  int sum = 0, k = __builtin_popcountll(mask);

  loop(i, 1, n-1) {
    sum += arr[i];
    if(arr[i] && !arr[i+1] && sum < k) {
      return 0;
    }
  }

  return 1;

}

void small_n() {
  ll lim = (1LL << n);

  loop(mask, 1, lim-1) {
    res[__builtin_popcountll(mask)] ^= is_cool(mask);
  }

}

struct StackFrame {
  ll x; int i;
};

constexpr int MAX_STACK = 50'000'000;

void rec(ll start_x, int start_i) {
  static StackFrame st[MAX_STACK];
  int stack_ptr = 1;

  st[stack_ptr] = { start_x, start_i };

  while(stack_ptr) {
    auto [ x, i ] = st[stack_ptr];
    ll tmp1 = (1LL << (edges[i].a - 1));
    ll tmp2 = (1LL << (edges[i].b - 1));

    if(i == (-1)) {
      res[__builtin_popcountll(x)] ^= 1;
      --stack_ptr;
      continue;
    }

    if(!(x & tmp1) && (x & tmp2)) {
      st[stack_ptr] = { x, i-1 };
      st[++stack_ptr] = { x ^ tmp1 ^ tmp2, i-1 };
      continue;
    }
    else if((x & tmp1) && !(x & tmp2)) {
      --stack_ptr; continue;
    }
    else {
      st[stack_ptr] = { x, i-1 }; continue;
    }

  }
}

void small_m() {

  loop_rev(len, n, 2) {
    loop(i, 0, n-len) {
      int j = i + len - 1;
      ll num = 0;
      loop(k, i, j) {
        num |= (1LL << k);
      }
      rec(num, m-1);
    }
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;

  loop(i, 0, m-1) {
    cin >> edges[i].a >> edges[i].b;
  }

  if(n <= 20) {
    small_n();
  }
  else {
    small_m();
  }

  cout << (n&1) << ' ';
  loop(i, 2, n) {
    cout << res[i] << ' ';
  }
  cout << '\n';

}