#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<pair<int, int>> ds[N];
vector<int> adj[N];
int dem[N], maxson[N], depth[N], ke[N][2], vx[N];
int mark[N], mi[N], mi_id[N];
bool active[N];
void maketree(int u, int pa) {
  dem[u] = 1;
  maxson[u] = 0;
  for (auto &p : adj[u]) {
    if (p == pa || depth[p] > 0) continue;
    maketree(p, u);
    dem[u] += dem[p];
    if (dem[maxson[u]] < dem[p]) maxson[u] = p;
  }
}
int get_centroid(int u) {
  int pa = 0;
  int n = dem[u];
  while (1) {
    if (maxson[u] == 0 || (dem[maxson[u]] << 1) <= n) break;
    pa = u;
    u = maxson[u];
  }
  return u;
}
void compute_path(int u, int pa) {
  dem[u] = 1;
  maxson[u] = 0;
  for (auto &p : adj[u]) {
    if (p == pa || depth[p] > 0) continue;
    compute_path(p, u);
    dem[u] += dem[p];
    if (dem[maxson[u]] < dem[p]) maxson[u] = p;
  }
}
void decompose(int root, int layer, int par) {
  root = get_centroid(root);
  depth[root] = layer;
  for (auto &p : adj[root]) {
    if (depth[p] > 0) continue;
    compute_path(p, 0);
    decompose(p, layer + 1, root);
  }
}
bool them(int v, int x, bool real = true) {
  if (ke[v][0] == x || ke[v][1] == x) return true;
  if (ke[v][1] > 0) return false;
  if (real) {
    if (ke[v][0] == 0)
      ke[v][0] = x;
    else
      ke[v][1] = x;
  }
  return true;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    ds[u].push_back({v, i + n});
    ds[v].push_back({u, i + n});
  }
  for (int i = 1; i <= n; i++) {
    if (i < n)
      ds[i].push_back({i + 1, i});
    else
      ds[i].push_back({1, n});
    if (i > 1)
      ds[i].push_back({i - 1, i - 1});
    else
      ds[i].push_back({n, n});
  }
  for (int i = 1; i <= n; i++) {
    sort(ds[i].begin(), ds[i].end());
  }
  int sz = 0;
  for (int bd = n; bd >= 1; bd--) {
    for (auto &u : ds[bd]) mark[u.first] = u.second;
    for (int i = (int)ds[bd].size() - 1; i >= 0; i--) {
      int u = ds[bd][i].first;
      if (u >= bd) continue;
      sz++;
      bool ok = true;
      int luu = u;
      int vv = ds[bd][i].second;
      if (active[vv] || !them(ds[bd][i].second, sz, false)) ok = false;
      int vxcnt = 0;
      vx[vxcnt++] = vv;
      while (ok) {
        int v = 0, nx = 0;
        if (u != luu && mark[u] > 0) {
          v = mark[u];
          nx = bd;
        } else if (ds[u][0].first < u && !active[ds[u][0].second]) {
          v = ds[u][0].second;
          nx = ds[u][0].first;
        }
        if (nx == 0) {
          ok = false;
          break;
        }
        vx[vxcnt++] = v;
        if (!them(v, sz, false)) {
          ok = false;
          break;
        }
        if (nx == bd) break;
        u = nx;
      }
      if (ok) {
        for (int i = 0; i < vxcnt; i++) {
          them(vx[i], sz);
          if (i < vxcnt - 1) active[vx[i]] = true;
        }
      } else
        sz--;
    }
    for (auto &u : ds[bd]) mark[u.first] = 0;
  }
  m += n;
  for (int i = 1; i <= m; i++) {
    if (ke[i][1] > 0 && ke[i][0] <= sz && ke[i][1] <= sz) {
      adj[ke[i][0]].push_back(ke[i][1]);
      adj[ke[i][1]].push_back(ke[i][0]);
    }
  }
  maketree(1, 0);
  decompose(1, 1, 0);
  for (int i = sz; i >= 1; i--) printf("%d ", depth[i]);
}
