#include <bits/stdc++.h>
using namespace std;
const int iinf = 1e9 + 7;
const long long linf = 1ll << 60;
const double dinf = 1e60;
template <typename T>
inline void scf(T &x) {
  bool f = 0;
  x = 0;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') {
    f = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  if (f) x = -x;
  return;
}
template <typename T1, typename T2>
void scf(T1 &x, T2 &y) {
  scf(x);
  return scf(y);
}
template <typename T1, typename T2, typename T3>
void scf(T1 &x, T2 &y, T3 &z) {
  scf(x);
  scf(y);
  return scf(z);
}
template <typename T1, typename T2, typename T3, typename T4>
void scf(T1 &x, T2 &y, T3 &z, T4 &w) {
  scf(x);
  scf(y);
  scf(z);
  return scf(w);
}
inline char mygetchar() {
  char c = getchar();
  while (c == ' ' || c == '\n') c = getchar();
  return c;
}
template <typename T>
void chkmax(T &x, const T &y) {
  if (y > x) x = y;
  return;
}
template <typename T>
void chkmin(T &x, const T &y) {
  if (y < x) x = y;
  return;
}
const int N = 1e5 + 100;
int n, m;
vector<int> g[N];
vector<int> rem[N];
int ord[N];
void MEI() {
  scf(n, m);
  static vector<int> polygon[N], used[N];
  for (int i = (1); i <= (n); ++i) polygon[i].clear();
  map<pair<int, int>, int> M;
  M.clear();
  for (int i = 0; i < (m); ++i) {
    int u, v;
    scf(u, v);
    polygon[u].push_back(v);
    polygon[v].push_back(u);
  }
  for (int i = (1); i <= (n); ++i) {
    polygon[i].push_back(i % n + 1);
    polygon[i % n + 1].push_back(i);
  }
  for (int i = (1); i <= (n); ++i) sort(polygon[i].begin(), polygon[i].end());
  for (int i = (1); i <= (n); ++i) {
    for (int j = 0; j < ((int)polygon[i].size()); ++j) used[i].push_back(0);
  }
  int tot = 0;
  for (int i = (1); i <= (n); ++i)
    for (int j = 0; j < ((int)polygon[i].size()); ++j)
      if (!used[i][j]) {
        int u = i, dir = j;
        vector<int> path;
        path.clear();
        while (!used[u][dir]) {
          path.push_back(u);
          int nxt_u = polygon[u][dir];
          int nxt_dir =
              (lower_bound(polygon[nxt_u].begin(), polygon[nxt_u].end(), u) -
               polygon[nxt_u].begin()) +
              1;
          used[u][dir] = 1;
          u = nxt_u;
          dir = nxt_dir % (int)polygon[u].size();
        }
        if (!tot) {
          tot++;
          continue;
        }
        tot++;
        ord[tot] = tot;
        rem[tot] = path;
        sort(rem[tot].begin(), rem[tot].end());
        reverse(rem[tot].begin(), rem[tot].end());
        for (int k = 0; k < ((int)path.size()); ++k) {
          int u = path[k], v = path[(k + 1) % (int)path.size()];
          if (u > v) swap(u, v);
          pair<int, int> t = make_pair(u, v);
          if (M.find(t) == M.end())
            M[t] = tot;
          else
            g[tot].push_back(M[t]), g[M[t]].push_back(tot);
        }
      }
  n = tot;
  return;
}
int ans[N];
bool vis[N];
int find_centroid(int u) {
  static int q[N], siz[N], hs[N], par[N];
  int fnt, rar;
  fnt = rar = 0;
  q[rar++] = u;
  par[u] = 0;
  while (fnt != rar) {
    u = q[fnt++];
    siz[u] = 1;
    hs[u] = 0;
    for (int v : g[u])
      if (!vis[v] && v != par[u]) par[v] = u, q[rar++] = v;
  }
  for (int i = (rar)-1; i >= 0; --i) {
    int u = q[i], v = par[u];
    chkmax(hs[u], rar - siz[u]);
    if (hs[u] * 2 <= rar) return u;
    siz[v] += siz[u];
    chkmax(hs[v], siz[u]);
  }
  return 0;
}
void dfs(int u = 2, int dep = 0) {
  u = find_centroid(u);
  ans[u] = dep + 1;
  vis[u] = 1;
  for (int v : g[u])
    if (!vis[v]) dfs(v, dep + 1);
  return;
}
void ZI() {
  sort(ord + 2, ord + n + 1, [&](int i, int j) {
    vector<int> &x = rem[i], &y = rem[j];
    for (int k = 0; k < (min((int)x.size(), (int)y.size())); ++k)
      if (x[k] != y[k]) return x[k] < y[k];
    return (int)x.size() < (int)y.size();
  });
  dfs();
  for (int i = (2); i <= (n); ++i) printf("%d ", ans[ord[i]]);
  return;
}
int main() {
  MEI();
  ZI();
  return 0;
}
