#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int N, M;
int add(int x, int y) {
  x += y;
  if (x >= N) {
    x -= N;
  }
  return x;
}
int subtr(int x, int y) {
  x -= y;
  if (x < 0) {
    x += N;
  }
  return x;
}
int len(pair<int, int> p) { return subtr(p.second, p.first); }
bool cmplen(pair<int, int> p1, pair<int, int> p2) { return len(p1) < len(p2); }
map<pair<int, int>, int> mpdiag;
pair<int, int> A[MAXN];
int nxt[MAXN];
bool dead[MAXN];
int ind[MAXN], pos[MAXN];
vector<int> sides[2 * MAXN];
vector<int> verts[2 * MAXN];
bool cmpvec(int x, int y) { return verts[x] < verts[y]; }
set<int> adj[MAXN];
int ans[MAXN];
int sz[MAXN];
void findcent(int x, int p, int s, int &cent) {
  bool found = true;
  sz[x] = 1;
  for (int y : adj[x]) {
    if (y == p) {
      continue;
    }
    findcent(y, x, s, cent);
    sz[x] += sz[y];
    if (sz[y] * 2 > s) {
      found = false;
    }
  }
  if (2 * (s - sz[x]) > s) {
    found = false;
  }
  if (found) {
    cent = x;
  }
}
void dfs(int x, int s, int c) {
  findcent(x, -1, s, x);
  ans[x] = c;
  vector<pair<int, int> > xadj;
  for (int y : adj[x]) {
    xadj.push_back({y, sz[y]});
  }
  adj[x].clear();
  for (pair<int, int> py : xadj) {
    adj[py.first].erase(x);
  }
  for (pair<int, int> py : xadj) {
    dfs(py.first, py.second, c + 1);
  }
}
int main() {
  scanf("%d %d", &N, &M);
  for (int i = 0; i < M; i++) {
    scanf("%d %d", &A[i].first, &A[i].second);
    A[i].first--;
    A[i].second--;
    if (len(A[i]) > N / 2) {
      swap(A[i].first, A[i].second);
    }
  }
  sort(A, A + M, cmplen);
  for (int i = 0; i < M; i++) {
    mpdiag[A[i]] = mpdiag[pair<int, int>(A[i].second, A[i].first)] = i;
  }
  for (int i = 0; i < N; i++) {
    nxt[i] = add(i, 1);
  }
  for (int i = 0; i < M; i++) {
    pair<int, int> p = A[i];
    for (int j = p.first;; j = nxt[j]) {
      if (j != p.first && j != p.second) {
        dead[j] = true;
      }
      verts[i].push_back(j);
      if (j == p.second) {
        break;
      }
      if (nxt[j] != add(j, 1)) {
        sides[mpdiag.at(pair<int, int>(j, nxt[j]))].push_back(i);
      }
    }
    nxt[p.first] = p.second;
    sides[i].push_back(i);
  }
  for (int vert = 0; vert < N; vert++) {
    if (dead[vert]) {
      continue;
    }
    int cur = vert;
    do {
      verts[M].push_back(cur);
      if (nxt[cur] != add(cur, 1)) {
        sides[mpdiag.at(pair<int, int>(cur, nxt[cur]))].push_back(M);
      }
      cur = nxt[cur];
    } while (cur != vert);
    break;
  }
  for (int i = 0; i <= M; i++) {
    sort(verts[i].rbegin(), verts[i].rend());
  }
  iota(ind, ind + M + 1, 0);
  sort(ind, ind + M + 1, cmpvec);
  for (int i = 0; i <= M; i++) {
    pos[ind[i]] = i;
  }
  for (int i = 0; i < M; i++) {
    assert(sides[i].size() == 2);
    int s0 = pos[sides[i][0]], s1 = pos[sides[i][1]];
    adj[s0].insert(s1);
    adj[s1].insert(s0);
  }
  dfs(0, N, 1);
  for (int i = 0; i <= M; i++) {
    printf("%d ", ans[i]);
  }
  puts("");
}
