#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n;
struct edge {
  int first, second;
  bool operator<(edge a) const {
    return first > a.first || (first == a.first && second > a.second);
  }
} a[N];
bool v[N];
int minsize, root, ncnt, size[N], lch[N], rch[N], lnum[N], rnum[N], color[N];
vector<int> e[N];
void dfs(int k, int n) {
  v[k] = size[k] = 1;
  int t = 0;
  for (vector<int>::iterator p = e[k].begin(); p != e[k].end(); p++)
    if (!v[*p]) {
      dfs(*p, n);
      size[k] += size[*p];
      t = max(t, size[*p]);
    }
  t = max(t, n - size[k]);
  if (t < minsize) {
    minsize = t;
    root = k;
  }
  v[k] = 0;
}
void getsize(int k) {
  v[k] = size[k] = 1;
  for (vector<int>::iterator p = e[k].begin(); p != e[k].end(); p++)
    if (!v[*p]) {
      getsize(*p);
      size[k] += size[*p];
    }
  v[k] = 0;
}
void divide(int k, int n, int dep) {
  minsize = n;
  dfs(k, n);
  k = root;
  getsize(k);
  v[k] = 1;
  color[k] = dep;
  for (vector<int>::iterator p = e[k].begin(); p != e[k].end(); p++)
    if (!v[*p]) divide(*p, size[*p], dep + 1);
}
void build(int k, int l, int r) {
  lnum[k] = l;
  rnum[k] = r;
  color[k] = 1;
  if (l == r) return;
  int mid = (l + r) >> 1;
  lch[k] = ++ncnt;
  build(ncnt, l, mid);
  rch[k] = ++ncnt;
  build(ncnt, mid + 1, r);
}
void update(int k, int c) { color[k] = c; }
void pushdown(int k) {
  if (color[k]) {
    update(lch[k], color[k]);
    update(rch[k], color[k]);
    color[k] = 0;
  }
}
void change(int k, int l, int r, int c) {
  if (l <= lnum[k] && r >= rnum[k]) {
    update(k, c);
    return;
  }
  pushdown(k);
  if (l < lnum[rch[k]]) change(lch[k], l, r, c);
  if (r > rnum[lch[k]]) change(rch[k], l, r, c);
}
int query(int k, int first) {
  if (lnum[k] == rnum[k]) return color[k];
  pushdown(k);
  if (first < lnum[rch[k]])
    return query(lch[k], first);
  else
    return query(rch[k], first);
}
int main() {
  int m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &a[i].first, &a[i].second);
    if (a[i].first < a[i].second) swap(a[i].first, a[i].second);
  }
  sort(a + 1, a + m + 1);
  ncnt = 0;
  build(0, 1, n);
  int R = n, C = 1;
  for (int i = 1; i <= m; i++)
    if (a[i].first == n) {
      ++C;
      int first = query(0, a[i].first);
      e[C].push_back(first);
      e[first].push_back(C);
      change(0, 1, a[i].second, C);
      change(0, a[i].first, n, C);
    } else {
      ++C;
      int first = query(0, a[i].first);
      if (i < m && a[i].first == a[i + 1].first) {
        e[C].push_back(C + 1);
        e[C + 1].push_back(C);
      } else {
        e[first].push_back(C);
        e[C].push_back(first);
      }
      if (i > 1 && a[i].first == a[i - 1].first)
        change(0, a[i].second + 1, a[i - 1].second, C);
      else
        change(0, a[i].second + 1, a[i].first - 1, C);
    }
  memset(v, 0, sizeof(v));
  divide(1, m + 1, 1);
  for (int i = m + 1; i; i--) printf("%d ", color[i]);
  return 0;
}
