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
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

struct vec {
  vector<char> elements;
  void init(int n) {
    elements.assign(n, '?');
  }
  char& operator [](int x) { return elements[x]; }
};

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  vector<pii> opers(m);
  
  for(auto &[a, b] : opers)
    cin >> a >> b,
    --a,
    --b;
    
  reverse(all(opers));
  reverse(all(opers)); // efectiv cum m-am prins de solutie
  // gen, daca vin din spate cu o solutie, ajung la primul si am doua elemente diferite, pot sa fac swap dupa sau nu, si obtin doua siruri care veneau din ceva valid
  // nu vreau asta, mi se anuleaza din paritate 
  
  vector<vec> elements;
  elements.emplace_back();
  elements.back().init(n);
  
  for(auto [a, b] : opers) {
    for(int i = 0; i < sz(elements); i++) {
      if(elements[i][a] == '?' && elements[i][b] == '?') {
        elements.emplace_back(elements[i]);
        elements.back()[a] = 0, elements.back()[b] = 0;
        elements.emplace_back(elements[i]);
        elements.back()[a] = 1, elements.back()[b] = 1;
        
        swap(elements[i], elements.back());
        elements.pop_back();
        i--;
        continue;
      }
      else if(elements[i][a] == 1 || elements[i][b] == 0)
        swap(elements[i][a], elements[i][b]);
    }
  }
  
  vector<int> rez(n + 1);
  for(auto v : elements) {
    int l = n, r = -1;
    for(int i = 0; i < n; i++)
      if(v[i] == 1) l = min(i, l), r = i;
    
    if(l > r) {
      vector<int> freq(n + 1);
      int last = -1;
      for(int i = 0; i < n; i++) {
        if(v[i] == 0) {
          freq[i - last - 1]++;
          last = i;
        }
      }
      freq[n - last - 1]++;
      for(int i = n; i > 0; i--)
        rez[i] += freq[i],
        freq[max(0, i - 2)] += freq[i];
    }
    
    else {
      bool acceptabil = 1;
      for(int i = l; i <= r; i++) {
        if(v[i] == 0) acceptabil = 0;
      }
      if(!acceptabil) continue;
      
      int extr = r + 1, extl = l - 1;
      while(extr < n && v[extr] != 0) extr++;
      while(extl >= 0 && v[extl] != 0) extl--;
      
      for(int lprim = extl + 1; lprim <= l; lprim++)
        for(int rprim = r; rprim < extr; rprim++)
          rez[rprim - lprim + 1]++;
    }
  }
  
  for(int i = 1; i <= n; i++)
    cout << rez[i] % 2 << ' ';
  cout << '\n';
  
  
  
  
  
  
}

/**
  Anul asta nu se da centroid
  -- Rugaciunile mele
*/