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
#include <bits/stdc++.h>

typedef long long int lli;

using namespace std;

#define MAX4 10010
#define MAX5 100010
#define MAX6 1000010

#define FOR(n) for (int i = 0; i < n; i++)

using vti = vector<int>;
using vts = vector<string>;

template <typename T> void dbg(T last) { cout << last << "\n"; }

template <typename T, typename... args> void dbg(T current, args... next) {
  cout << current << ' ';
  dbg(next...);
}

template <typename T> void getInput(vector<T> &v, int n, int x = 0) {
  for (int i = x; i < n; i++) {
    cin >> v[i];
  }
}

//-----------------------------------------------------------------------------------------------//
lli sum[40];
int n;
int m;
vector<pair<int, int>> tab;
bool test(lli x) {
  int cnt = __builtin_popcountll(x);
  // dbg("* ", x);
  for (auto [a, b] : tab) {
    a--;
    b--;
    if (((1LL << a) & x) && !((1LL << b) & x)) {
      x ^= (1LL << a);
      x ^= (1LL << b);
    }
  }
  int minn = INT_MAX, maxx = -1;
  for (int i = 0; i < n; i++) {
    if ((1LL << i) & x) {
      minn = min(minn, i);
    }

    if ((1LL << i) & x) {
      maxx = max(maxx, i);
    }
  }

  // dbg(x, cnt, maxx - minn + 1 == cnt);

  return maxx - minn + 1 == cnt;
}

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

  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    tab.push_back({a, b});
  }
  lli mask = (1LL << n) - 1;
  // dbg(n, mask);
  for (lli i = 0; i <= mask; i++) {
    int cnt = __builtin_popcountll(i);
    if (test(i)) {
      sum[cnt]++;
    }
  }

  for (int i = 1; i <= n; i++) {
    cout << sum[i] % 2 << " ";
  }
  cout << "\n";
}

int main() {
  std::ios::sync_with_stdio(false);

  solve();

  return 0;
}