#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int iter, dead[N], nxt[N], prv[N], ord[N], uwu[N], col[N];
vector<int> g[N], regions[N], edges[N];
int dfs(int v) {
  int u = v;
  while (true) {
    if (!dead[u] && !g[u].empty()) {
      dead[u] = true;
      int x = nxt[u];
      int y = prv[u];
      vector<int> vec, mep, men;
      vec.push_back(x);
      mep.push_back(prv[x]);
      men.push_back(nxt[x]);
      for (int z : g[u]) {
        vec.push_back(z);
        mep.push_back(prv[z]);
        men.push_back(nxt[z]);
      }
      vec.push_back(y);
      mep.push_back(prv[y]);
      men.push_back(nxt[y]);
      int preg = -1, ret = -1;
      for (int i = 1; i < vec.size(); i++) {
        int a = vec[i - 1];
        int b = vec[i];
        nxt[u] = a;
        prv[a] = u;
        nxt[b] = u;
        prv[u] = b;
        int creg = dfs(u);
        if (preg != -1) {
          edges[preg].push_back(creg);
          edges[creg].push_back(preg);
        }
        preg = creg;
        if (ret != -1) continue;
        int c = a;
        while (c != b) {
          if (c == v) {
            ret = creg;
            break;
          }
          c = nxt[c];
        }
      }
      for (int i = 0; i < vec.size(); i++) {
        nxt[vec[i]] = men[i];
        prv[vec[i]] = mep[i];
      }
      nxt[u] = x;
      prv[u] = y;
      assert(ret != -1);
      return ret;
    }
    u = prv[u];
    if (u == v) break;
  }
  u = v;
  ++iter;
  while (true) {
    regions[iter].push_back(u);
    u = prv[u];
    if (u == v) break;
  }
  return iter;
}
void dfs1(int v, int p) {
  uwu[v] = 1;
  for (int u : edges[v]) {
    if (u == p) continue;
    dfs1(u, v);
    uwu[v] += uwu[u];
  }
}
void dfs2(int v, int c) {
  int bg = -1;
  for (int u : edges[v]) {
    if (dead[u]) continue;
    if (bg == -1 || uwu[bg] < uwu[u]) bg = u;
  }
  if (bg == -1) {
    col[v] = c;
    dead[v] = true;
    return;
  }
  if (uwu[bg] <= uwu[v] / 2) {
    col[v] = c;
    dead[v] = true;
    for (int u : edges[v]) {
      if (!dead[u]) {
        dfs2(u, c + 1);
      }
    }
    return;
  }
  uwu[v] -= uwu[bg];
  uwu[bg] += uwu[v];
  dfs2(bg, c);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    if (a < b) swap(a, b);
    g[a].push_back(b);
  }
  for (int i = 1; i <= n; i++) {
    nxt[i] = i + 1;
    prv[i] = i - 1;
    dead[i] = false;
    if (i == 1) prv[i] = n;
    if (i == n) nxt[i] = 1;
    sort(g[i].begin(), g[i].end());
  }
  iter = 0;
  dfs(n);
  for (int i = 1; i <= iter; i++) {
    ord[i] = i;
    dead[i] = false;
    sort(regions[i].rbegin(), regions[i].rend());
  }
  sort(ord + 1, ord + iter + 1, [&](int i, int j) {
    int sz = min(regions[i].size(), regions[j].size());
    for (int k = 0; k < sz; k++) {
      if (regions[i][k] != regions[j][k]) return regions[i][k] < regions[j][k];
    }
    return regions[i].size() < regions[j].size();
  });
  dfs1(1, 0);
  dfs2(1, 1);
  for (int i = 1; i <= iter; i++) {
    cout << col[ord[i]] << " ";
  }
  cout << '\n';
  return 0;
}
