#include <bits/stdc++.h>
using namespace std;
const int inf = 1.01e9;
const double eps = 1e-9;
const int N = 4e5 + 10;
int f[N];
vector<int> e[N];
int n;
unordered_map<long long, int> M;
inline int& used(int x, int y) { return M[x * (1LL << (20)) + y]; }
void add(int x, int y) {
  if (y < x) y += n;
  e[x].push_back(y);
}
int id = 0;
vector<int> v[N];
void dfs(int x, int y) {
  if (used(x, y)) return;
  v[id].push_back(x);
  used(x, y) = 1;
  y %= n;
  if (x < y) x += n;
  int pos = lower_bound((e[y]).begin(), e[y].end(), x) - e[y].begin();
  assert(pos >= 0);
  pos--;
  dfs(y, e[y][pos]);
}
int p[N];
inline bool comp(int x, int y) { return v[x] < v[y]; }
unordered_map<long long, vector<int> > HA;
void ADD(int x, int y, int who) {
  if (x > y) swap(x, y);
  HA[x * (1LL << (20)) + y].push_back(who);
}
vector<int> t[N];
int cnt[N];
int dead[N];
void dfs1(int x, int xx) {
  cnt[x] = 1;
  for (int y : t[x]) {
    if (!dead[y] && y != xx) {
      dfs1(y, x);
      cnt[x] += cnt[y];
    }
  }
}
int OK(int x, int all) {
  if (2 * x <= all + 1) return 1;
  return 0;
}
int dfs2(int x, int xx, int all) {
  int ok = OK(all - cnt[x], all);
  for (int y : t[x]) {
    if (!dead[y] && y != xx) ok &= OK(cnt[y], all);
  }
  if (ok) return x;
  for (int y : t[x]) {
    if (!dead[y] && y != xx) {
      int r = dfs2(y, x, all);
      if (r != -1) return r;
    }
  }
  return -1;
}
int res[N];
void go(int x, int col = 1) {
  dfs1(x, -1);
  x = dfs2(x, -1, cnt[x]);
  res[x] = col;
  dead[x] = 1;
  for (int y : t[x])
    if (!dead[y]) go(y, col + 1);
}
int main() {
  int m;
  scanf("%d%d", &n, &m);
  for (int i = 0; (i) < (m); ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    --x, --y;
    add(x, y);
    add(y, x);
  }
  for (int i = 0; (i) < (n); ++i) {
    int x = i;
    int y = (i + 1) % n;
    add(x, y);
  }
  for (int i = 0; (i) < (n); ++i) {
    sort((e[i]).begin(), e[i].end());
  }
  for (int x = 0; (x) < (n); ++x)
    for (int y : e[x]) {
      if (used(x, y)) continue;
      dfs(x, y);
      if (((int)(v[id]).size()) == 1) {
        v[id].clear();
        continue;
      }
      for (int i = 0; (i) < (((int)(v[id]).size())); ++i) {
        int xx = v[id][i];
        int yy = v[id][(i + 1) % ((int)(v[id]).size())];
        ADD(xx, yy, id);
      }
      sort((v[id]).begin(), v[id].end());
      reverse((v[id]).begin(), v[id].end());
      id++;
    }
  for (int i = 0; (i) < (id); ++i) p[i] = i;
  sort(p, p + id, comp);
  for (auto it : HA) {
    if (((int)(it.second).size()) == 2) {
      int x = it.second[0];
      int y = it.second[1];
      t[x].push_back(y);
      t[y].push_back(x);
    }
  }
  go(0);
  for (int ii = 0; (ii) < (id); ++ii) {
    int i = p[ii];
    printf("%d%c", res[i], " \n"[ii + 1 == id]);
  }
  return 0;
}
