#include <bits/stdc++.h>
using namespace std;
template <typename T>
T getint() {
  T x = 0, p = 1;
  char ch;
  do {
    ch = getchar();
  } while (ch <= ' ');
  if (ch == '-') p = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * p;
}
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
template <typename T1, typename T2>
bool umin(T1 &x, const T2 &y) {
  if (x > y) return x = y, true;
  return false;
}
template <typename T1, typename T2>
bool umax(T1 &x, const T2 &y) {
  if (x < y) return x = y, true;
  return false;
}
const int maxn = (int)3e5 + 10;
const int inf = (int)1e9 + 5;
const int mod = (int)1e9 + 7;
const long long llinf = (long long)1e18 + 5;
const double pi = acos(-1.0);
vector<int> g[maxn];
vector<int> d[maxn];
vector<int> u[maxn];
int ans[maxn];
int was[maxn];
vector<int> nodes;
int par[maxn];
int sz[maxn];
void calcsz(int v, int p = -1) {
  nodes.push_back(v);
  sz[v] = 1;
  par[v] = p;
  for (int x : g[v]) {
    if (x == p || was[x]) continue;
    calcsz(x, v);
    sz[v] += sz[x];
  }
}
void build(int v, int depth = 1) {
  nodes.clear();
  calcsz(v);
  int c = -1;
  for (int x : nodes) {
    int mxsz = nodes.size() - sz[x];
    for (int v : g[x]) {
      if (v != par[x] && !was[v]) umax(mxsz, sz[v]);
    }
    if (mxsz <= nodes.size() / 2) c = x;
  }
  ans[c] = depth;
  was[c] = 1;
  for (int x : g[c]) {
    if (was[x]) continue;
    build(x, depth + 1);
  }
}
int main() {
  int n = getint<int>();
  int m = getint<int>();
  for (int i = (0); i < (m); i++) {
    int a = getint<int>() - 1;
    int b = getint<int>() - 1;
    d[a].push_back(b);
    d[b].push_back(a);
  }
  for (int i = (0); i < (n); i++) {
    d[i].push_back((i + 1) % n);
    d[i].push_back((i + n - 1) % n);
  }
  for (int i = (0); i < (n); i++) {
    sort((d[i]).begin(), (d[i]).end());
    u[i].resize(d[i].size());
  }
  auto nxt = [](const vector<int> &z, int x) -> int {
    auto iter = lower_bound((z).begin(), (z).end(), x);
    if (next(iter) == z.end()) return 0;
    return next(iter) - z.begin();
  };
  vector<vector<int> > regs;
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (d[i].size()); j++) {
      if (u[i][j]) continue;
      vector<int> r;
      int v = i, x = j;
      while (!u[v][x]) {
        r.push_back(v);
        u[v][x] = true;
        int to = d[v][x];
        int z = nxt(d[to], v);
        v = to;
        x = z;
      }
      if (r.size() == n &&
          (m != 0 || (regs.size() > 0 && regs.back().size() == n)))
        continue;
      sort((r).begin(), (r).end());
      reverse((r).begin(), (r).end());
      regs.push_back(r);
    }
  }
  sort((regs).begin(), (regs).end());
  map<pair<int, int>, int> have;
  for (int i = (0); i < (regs.size()); i++) {
    int m = regs[i].size();
    for (int j = (0); j < (m); j++) {
      pair<int, int> z = minmax(regs[i][j], regs[i][(j + 1) % m]);
      if (have.count(z)) {
        g[i].push_back(have[z]);
        g[have[z]].push_back(i);
      }
      have[z] = i;
    }
  }
  build(0);
  for (int i = (0); i < (regs.size()); i++) {
    printf("%d ", ans[i]);
  }
  return 0;
}
