#include <bits/stdc++.h>
using namespace std;
vector<int> g[100005];
vector<int> g2[100005];
vector<int> c[100005];
map<pair<int, int>, int> w;
pair<vector<int>, int> t[100005];
int n, m, nr;
void doit(int x, int y) {
  int xx = x;
  c[nr].push_back(x);
  w[make_pair(x, y)] = nr;
  while (y != xx) {
    c[nr].push_back(y);
    int k = lower_bound(g[y].begin(), g[y].end(), x) - g[y].begin();
    x = y;
    y = g[y][(k + 1) % g[y].size()];
    w[make_pair(x, y)] = nr;
  }
  if (c[nr].size() == n) {
    for (int i = 0, ThxDem = c[nr].size(); i < ThxDem; ++i)
      w[make_pair(c[nr][i], c[nr][(i + 1) % n])] = -1;
    c[nr].clear();
  } else
    nr++;
}
int r[100005];
bool tk[100005];
int fat[100005];
int szt[100005];
int calcsz(int x, int f) {
  szt[x] = 1;
  for (auto y : g2[x])
    if (y != f && !tk[y]) szt[x] += calcsz(y, x);
  return szt[x];
}
void cdfs(int x = 0, int f = -1, int sz = -1, int k = 1) {
  if (sz < 0) sz = calcsz(x, -1);
  for (auto y : g2[x])
    if (!tk[y] && szt[y] * 2 >= sz) {
      szt[x] = 0;
      cdfs(y, f, sz, k);
      return;
    }
  tk[x] = true;
  fat[x] = f;
  r[x] = k;
  for (auto y : g2[x])
    if (!tk[y]) cdfs(y, x, -1, k + 1);
}
void centroid() {
  memset(tk, false, sizeof(tk));
  cdfs();
}
int main() {
  scanf("%d%d", &n, &m);
  if (m == 0) {
    puts("1");
    return 0;
  }
  for (int i = 0, ThxDem = m; i < ThxDem; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 0, ThxDem = n; i < ThxDem; ++i)
    g[i].push_back((i + 1) % n), g[(i + 1) % n].push_back(i);
  for (int i = 0, ThxDem = n; i < ThxDem; ++i) sort(g[i].begin(), g[i].end());
  for (int x = 0, ThxDem = n; x < ThxDem; ++x)
    for (int y : g[x])
      if (!w.count(make_pair(x, y))) doit(x, y);
  assert(nr == m + 1);
  for (int i = 0, ThxDem = nr; i < ThxDem; ++i) {
  }
  for (int x = 0, ThxDem = nr; x < ThxDem; ++x) {
    for (int j = 0, ThxDem = c[x].size(); j < ThxDem; ++j) {
      int y = w[make_pair(c[x][(j + 1) % c[x].size()], c[x][j])];
      if (y >= 0) g2[x].push_back(y);
    }
    vector<int> q = c[x];
    sort(q.begin(), q.end());
    reverse(q.begin(), q.end());
    for (int i = 0, ThxDem = q.size(); i < ThxDem; ++i) q[i] = -q[i];
    t[x] = make_pair(q, x);
  }
  sort(t, t + nr);
  reverse(t, t + nr);
  centroid();
  for (int i = 0, ThxDem = nr; i < ThxDem; ++i) {
    if (i) putchar(' ');
    printf("%d", r[t[i].second]);
  }
  puts("");
  return 0;
}
