#include <bits/stdc++.h>
#pragma GCC optimize("03")
using namespace std;
struct Graph {
  int first, last, n;
  vector<vector<int>> adj;
  Graph(int n, bool base) : first(base), last(n + base), n(n), adj(last) {}
  void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  void addArc(int u, int v) { adj[u].push_back(v); }
};
struct CentroidDecomposition {
  Graph g;
  vector<int> sz;
  vector<bool> cut;
  vector<int> lvl;
  CentroidDecomposition(Graph&& g)
      : g(g), sz(g.last), cut(g.last), lvl(g.last) {
    solve(g.first, g.first, 0);
  }
  void sizes(int u, int par) {
    sz[u] = 1;
    for (int v : g.adj[u]) {
      if (v == par || cut[v]) continue;
      sizes(v, u);
      sz[u] += sz[v];
    }
  }
  int find(int u, int par, int cnt) {
    for (int v : g.adj[u]) {
      if (v == par || cut[v]) continue;
      if (sz[v] << 1 > cnt) return find(v, u, cnt);
    }
    return u;
  }
  template <class F>
  void halfPaths(int u, int par, int d, const F& get) {
    get(u, d);
    for (int v : g.adj[u]) {
      if (v == par || cut[v]) continue;
      halfPaths(v, u, d + 1, get);
    }
  }
  void solve(int c, int par, int h) {
    sizes(c, par);
    c = find(c, par, sz[c]);
    cut[c] = true;
    lvl[c] = h;
    for (int r : g.adj[c]) {
      if (!cut[r]) solve(r, c, h + 1);
    }
  }
};
template <class T>
struct DisjointRanges {
  map<int, pair<int, T>> s;
  vector<tuple<int, int, T>> update(int l, int r, T x) {
    vector<tuple<int, int, T>> bye;
    auto last = s.upper_bound(r);
    if (last != s.begin()) {
      auto it = prev(last);
      if (it->second.first > r) {
        last = s.emplace_hint(last, r + 1, it->second);
        it->second.first = r;
      }
    }
    auto first = s.lower_bound(l);
    if (first != s.begin()) {
      auto it = prev(first);
      if (it->second.first >= l) {
        bye.push_back({l, it->second.first, it->second.second});
        it->second.first = l - 1;
      }
    }
    for (auto it = first; it != last; it = s.erase(it)) {
      bye.push_back({it->first, it->second.first, it->second.second});
    }
    s.emplace_hint(last, l, make_pair(r, x));
    return bye;
  }
};
template <typename T>
struct CoordinateCompression {
  vector<T> o;
  void push(const T& x) { o.push_back(x); }
  int build() {
    sort(o.begin(), o.end());
    o.erase(unique(o.begin(), o.end()), o.end());
    return o.size();
  }
  int operator()(const T& x) {
    auto it = lower_bound(o.begin(), o.end(), x);
    return it == o.end() || x < *it ? -1 : it - o.begin();
  }
  T& operator[](int i) { return o[i]; }
};
vector<pair<int, int>> shortest(int l, int r, int n) {
  vector<pair<int, int>> ans;
  int len = r - l - 1;
  if (len < n - 2 - len) {
    ans.emplace_back(l, r - 1);
  } else {
    ans.emplace_back(r, n);
    if (l > 1) ans.emplace_back(1, l - 1);
  }
  return ans;
}
int length(int l, int r, int n) {
  int aux = r - l - 1;
  return min(aux, n - 2 - aux);
}
pair<int, int> better(pair<int, int> cur, pair<int, int> alt) {
  set<int> s({cur.first, cur.second, alt.first, alt.second});
  return {*s.rbegin(), *(++s.rbegin())};
}
int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> diag;
  for (int i = 0; i < m; i++) {
    int l, r;
    cin >> l >> r;
    if (l > r) swap(l, r);
    diag.emplace_back(l, r);
  }
  sort(diag.begin(), diag.end(),
       [&](const pair<int, int>& a, const pair<int, int>& b) {
         return length(a.first, a.second, n) < length(b.first, b.second, n);
       });
  CoordinateCompression<pair<int, int>> cc;
  DisjointRanges<int> dr;
  dr.update(1, n, -1);
  vector<vector<int>> adj(m + 1);
  vector<pair<int, int>> rank(m + 1);
  for (int u = 0; u <= m; u++) {
    vector<pair<int, int>> upd;
    if (u == m) {
      upd = {{1, n}};
    } else {
      auto [l, r] = diag[u];
      rank[u] = {r, l};
      upd = shortest(l, r, n);
    }
    for (auto [ul, ur] : upd) {
      for (auto [ql, qr, v] : dr.update(ul, ur, u)) {
        if (v == -1) {
          pair<int, int> alt;
          if (qr == n) {
            if (ql == n) {
              alt = {n, 1};
            } else {
              alt = {n, n - 1};
            }
          } else {
            alt = {qr + 1, qr};
          }
          rank[u] = better(rank[u], alt);
        } else {
          rank[u] = better(rank[u], diag[v]);
          adj[u].push_back(v);
        }
      }
    }
    sort(adj[u].begin(), adj[u].end());
    adj[u].erase(unique(adj[u].begin(), adj[u].end()), adj[u].end());
    cc.push(rank[u]);
  }
  cc.build();
  Graph g(m + 1, 0);
  for (int u = 0; u <= m; u++) {
    int i = cc(rank[u]);
    for (int v : adj[u]) {
      int j = cc(rank[v]);
      g.addEdge(i, j);
    }
  }
  CentroidDecomposition cd(move(g));
  for (int i = 0; i <= m; i++) cout << cd.lvl[i] + 1 << ' ';
}
