#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 1e6 + 6;
vector<int> q[N];
map<int, int> pos[N];
vector<int> r[N];
vector<int> g[N];
int ans[N];
int sz[N];
int u[N];
vector<int> a;
int pp[N];
void dfs(int v, int par = -1) {
  a.push_back(v);
  pp[v] = par;
  u[v] = 1;
  sz[v] = 1;
  for (int i : g[v])
    if (!ans[i]) {
      if (i == par) continue;
      if (!u[i]) {
        dfs(i, v);
        sz[v] += sz[i];
      }
    }
}
int nb[N];
void go(int v, int lim) {
  a.clear();
  dfs(v);
  int c = -1, all = a.size();
  if (all == 1) {
    ans[v] = lim;
    return;
  }
  vector<int> lv;
  for (int v : a) {
    int mx = all - sz[v];
    nb[v] = 0;
    for (int i : g[v])
      if (!ans[i]) {
        ++nb[v];
        if (i == pp[v]) continue;
        mx = max(mx, sz[i]);
      }
    if (mx * 2 <= all) c = v;
    if (nb[v] == 1) lv.push_back(v);
    u[v] = 0;
  }
  assert(c != -1);
  ans[c] = lim;
  for (int i : g[c])
    if (!ans[i]) {
      go(i, lim + 1);
    }
}
pair<int, int> ff(int x, int y) { return make_pair(min(x, y), max(x, y)); }
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int k = 0; k < m; ++k) {
    int i, j;
    cin >> i >> j;
    q[i].push_back(j);
    q[j].push_back(i);
  }
  for (int i = 1; i <= n; ++i) {
    int j = i == n ? 1 : i + 1;
    q[i].push_back(j);
    q[j].push_back(i);
  }
  for (int i = 1; i <= n; ++i) {
    sort((q[i]).begin(), (q[i]).end());
    vector<int> v;
    for (int x : q[i])
      if (x > i) v.push_back(x);
    for (int x : q[i])
      if (x < i) v.push_back(x);
    for (int k = 0; k < v.size(); ++k) pos[i][v[k]] = k;
    q[i] = v;
  }
  set<pair<int, int>> us;
  map<pair<int, int>, vector<int>> con;
  int cnt = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j : q[i]) {
      if ((i - 1 + n - 1) % n == j - 1) continue;
      auto p = make_pair(i, j);
      if (us.count(p)) continue;
      auto &w = r[cnt];
      w = {i};
      int x = i, y = j;
      for (; y != i;) {
        w.push_back(y);
        int k = pos[y][x] - 1;
        if (k == -1) k = q[y].size() - 1;
        int z = q[y][k];
        x = y;
        y = z;
      }
      for (int k = 1; k < w.size(); ++k) us.insert({w[k - 1], w[k]});
      us.insert({w.back(), w[0]});
      for (int k = 1; k < w.size(); ++k) con[ff(w[k - 1], w[k])].push_back(cnt);
      con[ff(w.back(), w[0])].push_back(cnt);
      sort((w).begin(), (w).end());
      reverse((w).begin(), (w).end());
      ++cnt;
    }
  }
  vector<int> per(cnt), perpos(cnt);
  for (int i = 0; i < cnt; ++i) per[i] = i;
  sort((per).begin(), (per).end(), [](int i, int j) { return r[i] < r[j]; });
  for (int k = 0; k < cnt; ++k) {
    int i = per[k];
    perpos[i] = k;
  }
  for (auto p : con) {
    auto &v = p.second;
    if (v.size() == 1) continue;
    int x = v[0], y = v[1];
    x = perpos[x];
    y = perpos[y];
    g[x].push_back(y);
    g[y].push_back(x);
  }
  go(0, 1);
  for (int i = 0; i < cnt; ++i) cout << ans[i] << ' ';
  return 0;
}
