#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
int n, m, reg, col[N];
vector<int> diag[N], g[N];
map<long long, int> mp;
long long imp[N];
inline long long Encode(int x, int y, int z) {
  long long a[3] = {x, y, z};
  sort(a, a + 3, greater<long long>());
  return (a[0] << 40) | (a[1] << 20) | a[2];
}
int GetTriplet(int x, int y, int z) {
  long long hashVal = Encode(x, y, z);
  if (mp.find(hashVal) == mp.end()) {
    ++reg;
    while (true) {
      z = *prev(upper_bound(
          diag[x].begin(), diag[x].end(), z,
          [&](int a, int b) { return (x - a + n) % n < (x - b + n) % n; }));
      swap(x, z), swap(y, z);
      long long curHash = Encode(x, y, z);
      if (mp.find(curHash) != mp.end())
        break;
      else
        mp.insert({curHash, reg});
      imp[reg] = max(imp[reg], curHash);
    }
  }
  return mp[hashVal];
}
void BuildTree() {
  for (int i = 1; i <= n; ++i) {
    diag[i].push_back(i % n + 1);
    diag[i].push_back((i - 2 + n) % n + 1);
    sort(diag[i].begin(), diag[i].end(),
         [&](int a, int b) { return (i - a + n) % n < (i - b + n) % n; });
  }
  for (int i = n; i >= 1; --i)
    for (int j = 1; j < diag[i].size() - 1; ++j) {
      int u = GetTriplet(diag[i][j - 1], i, diag[i][j]);
      int v = GetTriplet(diag[i][j], i, diag[i][j + 1]);
      g[u].push_back(v);
      g[v].push_back(u);
    }
}
int sze[N];
bool chk[N];
int Dfs1(int u, int p) {
  sze[u] = 1;
  for (int v : g[u])
    if (v != p && !chk[v]) sze[u] += Dfs1(v, u);
  return sze[u];
}
void Dfs2(int u, int par, int root, int dep) {
  for (int v : g[u])
    if (v != par && !chk[v] && sze[v] * 2 > sze[root])
      return Dfs2(v, u, root, dep);
  chk[u] = true;
  col[u] = dep;
  for (int v : g[u])
    if (!chk[v]) {
      Dfs1(v, u);
      Dfs2(v, u, v, dep + 1);
    }
}
int main() {
  scanf("%d %d", &n, &m);
  if (m > 0) {
    for (int i = 0; i < m; ++i) {
      int u, v;
      scanf("%d %d", &u, &v);
      diag[u].push_back(v);
      diag[v].push_back(u);
    }
    BuildTree();
    for (int i = 1; i <= reg; ++i) {
      sort(g[i].begin(), g[i].end());
      g[i].resize(unique(g[i].begin(), g[i].end()) - g[i].begin());
    }
    Dfs1(1, 0);
    Dfs2(1, 0, 1, 1);
    vector<int> ids;
    for (int i = 1; i <= reg; ++i) ids.push_back(i);
    sort(ids.begin(), ids.end(), [&](int a, int b) { return imp[a] < imp[b]; });
    for (int i = 1; i <= reg; ++i) printf("%d ", col[ids[i - 1]]);
  } else
    printf("1");
  return 0;
}
