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

#define debug if (0)

using namespace std;

enum val {
  UNKNOWN = 0,
  ZERO = 1,
  ONE = 2,
};

const int MAXN = 35;
const int MAXC = (1 << 17) + 100;

val constraints[MAXC][MAXN];
bool res[MAXN];
int cnt = 1, n, m;

// Pesymistycznie ~ m2^(n/2)
void apply_constraint(const int x, const int y) {
  int extra = 0;
  for (int c = 0; c < cnt; ++c) {
    val *const con = constraints[c];
    if (con[x] == ONE || con[y] == ZERO) {
      swap(con[x], con[y]);
    } else if (con[x] == UNKNOWN && con[y] == UNKNOWN) {
      memcpy(constraints[cnt + extra], con, n * sizeof(val));
      con[x] = con[y] = ZERO;
      constraints[cnt + extra][x] = ONE, constraints[cnt + extra][y] = ONE;
      ++extra;
    }
  }
  cnt += extra;
}

// Pesymistycznie ~ n 2^(n/2)
void calc_res() {
  for (int c = 0; c < cnt; ++c) {
    val *const con = constraints[c];
    int left = n, right = 0;
    for (int i = 0; i < n; ++i)
      if (con[i] == ONE)
        left = min(left, right = i);

    int ll = left, rr = right + 1;

    // case 1: no ONE
    if (left > right) {
      debug { cout << "cons " << c << endl; }
      int i = 0, j = 0;
      while (i < n) {
        debug { cout << "i, j: " << i << ' ' << j << '\n'; }
        if (con[i] == ZERO) {
          ++i, ++j;
          continue;
        }
        if (j == n || con[j] == ZERO) {
          for (int d = j - i - 1; d >= 0; d -= 2) {
            debug { cout << "flip res[" << d << "]\n"; }
            res[d] ^= 1;
          }
          i = ++j;
          continue;
        }
        ++j;
      }
      continue;
    }

    bool end_loop = false;
    // case 2: at least 1 ONE
    for (int i = left + 1; i < right; ++i)
      if (con[i] == ZERO) {
        end_loop = true;
        break;
      }
    if (end_loop) {
      continue;
    }

    while (ll > 0 && con[ll - 1] != ZERO)
      --ll;
    while (rr < n && con[rr] != ZERO)
      ++rr;
    for (int d = right - left; d < rr - ll; ++d) {
      const int y = min(rr, left + d + 1);
      const int x = max(ll, right - d);
      res[d] ^= (y - x - d) & 1;
      debug {
        cout << "x, y, l, r, ll, rr: " << x << ' ' << y << ' ' << left << ' '
             << right << ' ' << ll << ' ' << rr << endl;
        cout << "after res[" << d << "] = " << res[d] << '\n';
      }
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    apply_constraint(x - 1, y - 1);
  }

  debug {
    for (int i = 0; i < cnt; ++i) {
      for (int j = 0; j < n; ++j)
        cout << constraints[i][j] << ' ';
      cout << '\n';
    }
  }

  calc_res();
  for (int i = 0; i < n; ++i)
    cout << res[i] << ' ';
  cout << '\n';
}