#include <bits/stdc++.h>
using namespace std;
struct node {
  int y, next;
} a[200010];
int first[100010], len, id;
map<long long, int> z;
vector<long long> b[100010];
vector<int> to[100010];
int T[100010], tl, now;
int mark[100010];
int size[100010];
void ins(int x, int y) {
  a[++len].y = y;
  a[len].next = first[x];
  first[x] = len;
}
int cmp(const void *xx, const void *yy) {
  int x = *(int *)xx, y = *(int *)yy;
  if (x < now && y > now) return -1;
  if (x > now && y < now) return 1;
  return y - x;
}
void dfs_root(int x, int fa, int sum, int &root) {
  int k, y, ok = 1;
  size[x] = 1;
  for (k = first[x]; k; k = a[k].next) {
    y = a[k].y;
    if (y == fa || mark[y]) continue;
    dfs_root(y, x, sum, root);
    if (size[y] * 2 > sum) ok = 0;
    size[x] += size[y];
  }
  if ((sum - size[x]) * 2 > sum) ok = 0;
  if (ok) root = x;
}
void dfs(int x, int sum, int d) {
  dfs_root(x, 0, sum, x);
  mark[x] = d;
  int k, y;
  for (k = first[x]; k; k = a[k].next) {
    y = a[k].y;
    if (mark[y]) continue;
    dfs(y, size[y] * 2 > sum ? sum - size[x] : size[y], d + 1);
  }
}
int main() {
  int n, m, i, j, x, y;
  long long s;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &x, &y);
    to[x].push_back(y);
    to[y].push_back(x);
  }
  for (i = 1; i < n; i++) {
    to[i].push_back(i + 1);
    to[i + 1].push_back(i);
  }
  to[n].push_back(1);
  to[1].push_back(n);
  for (i = n; i >= 1; i--) {
    tl = 0;
    for (j = 0; j < to[i].size(); j++) T[++tl] = to[i][j];
    now = i;
    qsort(T + 1, tl, sizeof(int), cmp);
    for (j = 1; j < tl; j++) {
      x = T[j + 1];
      y = T[j];
      if (!z.count((long long)(i - 1) * n + x - 1)) {
        z[(long long)(i - 1) * n + x - 1] = ++id;
        b[id].push_back((long long)(i - 1) * n + x - 1);
      }
      now = z[(long long)(i - 1) * n + x - 1];
      if (!z.count((long long)(y - 1) * n + i - 1)) {
        z[(long long)(y - 1) * n + i - 1] = now;
        b[now].push_back((long long)(y - 1) * n + i - 1);
      }
    }
  }
  for (i = 1; i <= id; i++) {
    for (j = 0; j < b[i].size(); j++) {
      s = b[i][j];
      x = s / n + 1;
      y = s % n + 1;
      if (z.count((long long)(y - 1) * n + x - 1))
        ins(i, z[(long long)(y - 1) * n + x - 1]);
    }
  }
  dfs(1, id, 1);
  for (i = id; i >= 1; i--) printf("%d ", mark[i]);
  printf("\n");
  return 0;
}
