#include <bits/stdc++.h>
using namespace std;
const long long siz = 1e5 + 10;
long long n, m;
struct info {
  long long v1, v2;
} diag[siz];
const bool operator<(const info &a, const info &b) {
  long long aTotalNodes = min(a.v2 - a.v1 - 1, n - 2 - (a.v2 - a.v1 - 1));
  long long bTotalNodes = min(b.v2 - b.v1 - 1, n - 2 - (b.v2 - b.v1 - 1));
  return aTotalNodes < bTotalNodes;
}
vector<int> region[siz];
unordered_map<int, int> dreg[siz];
const long long MAX = 1e5;
vector<long long> g[MAX + 9];
long long del[MAX + 9], sz[MAX + 9], par[MAX + 9], curSize, col[siz];
void dfs(long long u, long long p) {
  sz[u] = 1;
  for (long long i = 0; i < g[u].size(); i++) {
    long long nd = g[u][i];
    if (nd == p || del[nd]) continue;
    dfs(nd, u);
    sz[u] += sz[nd];
  }
}
long long findCentroid(long long u, long long p) {
  for (long long i = 0; i < g[u].size(); i++) {
    long long nd = g[u][i];
    if (nd == p || del[nd] || sz[nd] <= curSize / 2) continue;
    return findCentroid(nd, u);
  }
  return u;
}
void decompose(long long u, long long p, long long lev) {
  dfs(u, -1);
  curSize = sz[u];
  long long cen = findCentroid(u, -1);
  if (p == -1) p = cen;
  par[cen] = p, del[cen] = 1, col[cen] = lev;
  for (long long i = 0; i < g[cen].size(); i++) {
    long long nd = g[cen][i];
    if (!del[nd]) decompose(nd, cen, lev + 1);
  }
}
int main() {
  cin >> n >> m;
  for (long long i = 1; i <= m; ++i) {
    long long u, v;
    scanf("%lld", &u), scanf("%lld", &v);
    if (u > v) swap(u, v);
    diag[i] = {u, v};
  }
  sort(diag + 1, diag + m + 1);
  set<int> vertex;
  for (long long i = 1; i <= n; ++i) vertex.insert(i);
  for (long long i = 1; i <= m; ++i) {
    long long dwn = diag[i].v2 - diag[i].v1 - 1, up = n - 2 - dwn;
    if (dwn <= up) {
      region[i].push_back(diag[i].v1);
      auto it = vertex.upper_bound(diag[i].v1);
      while (*it != diag[i].v2) region[i].push_back(*it), ++it;
      region[i].push_back(diag[i].v2);
      for (long long j = 1; j + 1 < region[i].size(); j++)
        vertex.erase(region[i][j]);
    } else {
      while (*vertex.begin() != diag[i].v1) {
        region[i].push_back(*vertex.begin());
        vertex.erase(vertex.begin());
      }
      region[i].push_back(diag[i].v1);
      while (*vertex.rbegin() != diag[i].v2) {
        region[i].push_back(*vertex.rbegin());
        vertex.erase(*vertex.rbegin());
      }
      region[i].push_back(diag[i].v2);
    }
    sort(region[i].begin(), region[i].end(), greater<int>());
  }
  long long idx = m + 1;
  while (!vertex.empty()) {
    region[idx].push_back(*vertex.rbegin());
    vertex.erase(*vertex.rbegin());
  }
  sort(region + 1, region + idx + 1);
  for (long long i = 1; i <= idx; ++i) {
    for (int j = 0; j < region[i].size(); j++) {
      int nxt = (j + 1) % region[i].size();
      int v1 = region[i][j], v2 = region[i][nxt];
      if (v1 > v2) swap(v1, v2);
      if (dreg[v1].find(v2) == dreg[v1].end())
        dreg[v1][v2] = i;
      else {
        int reg = dreg[v1][v2];
        g[reg].push_back(i);
        g[i].push_back(reg);
      }
    }
  }
  decompose(1, -1, 1);
  for (long long i = 1; i <= idx; ++i) {
    if (i != 1) printf(" ");
    printf("%lld", col[i]);
  }
  printf("\n");
  return 0;
}
