#include <bits/stdc++.h>
using namespace std;
const int Q = 1 << 17;
int las[Q], e[Q << 1], nn[Q << 1], inc = 0;
void ins(int x, int y) {
  e[++inc] = y;
  nn[inc] = las[x];
  las[x] = inc;
}
unordered_map<int, int> bok[Q];
vector<int> g[Q], tw[Q], uz;
int maxn = 0;
long long va[Q];
int tid[Q], dd[Q];
bool cmp(int a, int b) { return va[a] < va[b]; }
int ans[Q], iid, mn, del[Q];
int si[Q];
void Gra(int x, int last, int sizz) {
  si[x] = 1;
  int mx = 0;
  for (int t = las[x]; t; t = nn[t]) {
    int y = e[t];
    if (y == last || del[y]) continue;
    Gra(y, x, sizz);
    si[x] += si[y];
    mx = max(mx, si[y]);
  }
  mx = max(mx, sizz - si[x]);
  if (mx < mn) mn = mx, iid = x;
}
void dfs(int x, int last) {
  si[x] = 1;
  for (int t = las[x]; t; t = nn[t]) {
    int y = e[t];
    if (y == last || del[y]) continue;
    dfs(y, x), si[x] += si[y];
  }
}
void DC(int x, int sizz, int dep) {
  mn = 1e9, Gra(x, 0, sizz), x = iid, del[x] = 1, ans[x] = dep;
  for (int t = las[x]; t; t = nn[t]) {
    int y = e[t];
    if (del[y]) continue;
    dfs(y, x);
    DC(y, si[y], dep + 1);
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    g[i % n + 1].push_back(i), g[i].push_back(i % n + 1);
  for (int i = 1, x, y; i <= m; i++)
    scanf("%d%d", &x, &y), g[x].push_back(y), g[y].push_back(x);
  for (int i = 1; i <= n; i++) {
    sort(g[i].begin(), g[i].end());
    for (int j = 0; j < (int)g[i].size(); j++)
      tw[i].push_back(0), bok[i][g[i][j]] = j;
  }
  long long b1 = 1e6, b2 = (long long)1e12;
  for (int u = 1; u <= n; u++)
    for (int v = 0; v < (int)g[u].size(); v++) {
      if (tw[u][v]) continue;
      int now = g[u][v], lst = u;
      if (u % n + 1 == now) continue;
      tw[u][v] = ++maxn;
      uz.resize(1);
      uz[0] = now;
      while (now != u) {
        int pid = bok[now][lst] + 1;
        if (pid == (int)g[now].size()) pid = 0;
        tw[now][pid] = maxn;
        lst = now, now = g[now][pid];
        uz.push_back(now);
      }
      sort(uz.begin(), uz.end());
      int sz = uz.size() - 1;
      va[maxn] = b2 * uz[sz] + b1 * uz[sz - 1] + uz[sz - 2];
    }
  for (int i = 1; i <= maxn; i++) tid[i] = i;
  sort(tid + 1, tid + maxn + 1, cmp);
  for (int i = 1; i <= maxn; i++) dd[tid[i]] = i;
  for (int x = 1; x <= n; x++)
    for (int i = 0; i < (int)g[x].size(); i++) {
      int y = g[x][i];
      if (x > y || x + 1 == y || (x == 1 && y == n)) continue;
      int j = bok[y][x];
      ins(dd[tw[x][i]], dd[tw[y][j]]), ins(dd[tw[y][j]], dd[tw[x][i]]);
    }
  DC(1, maxn, 1);
  for (int i = 1; i <= maxn; i++) printf("%d ", ans[i]);
  return 0;
}
