#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, sz[N], g[N], f[N];
bool pd[N];
vector<int> v[N];
pair<int, int> e[N];
bool cmp(pair<int, int> a, pair<int, int> b) {
  return a.first > b.first || a.first == b.first && a.second < b.second;
}
int tot;
stack<int> s, s1;
struct tri {
  int x, y, z;
  tri(int a = 0, int b = 0, int c = 0) : x(a), y(b), z(c) {}
} q[N];
int find(int x, int fa, int tot) {
  int t, ret = -1, tmp;
  sz[x] = 1;
  bool pd2 = true;
  for (int i = 0; i < v[x].size(); i++)
    if ((t = v[x][i]) != fa && pd[t]) {
      tmp = find(t, x, tot);
      sz[x] += sz[t];
      if (sz[t] > (tot >> 1)) pd2 = false;
      if (tmp != -1) ret = tmp;
    }
  if ((tot - sz[x]) > (tot >> 1)) pd2 = false;
  if (pd2) ret = x;
  return ret;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (x < y) swap(x, y);
    e[i] = make_pair(x, y);
  }
  sort(e + 1, e + m + 1, cmp);
  e[0] = make_pair(n, 1);
  if (m == 0 || n > e[1].first)
    g[++tot] = 0;
  else
    s1.push(0);
  s.push(0);
  for (int i = 1; i <= m; i++) {
    if (e[i].first < e[s.top()].first) {
      while (!s1.empty()) {
        g[++tot] = s1.top();
        s1.pop();
      }
    }
    while (e[s.top()].second >= e[i].first) s.pop();
    if (i < m && e[i + 1].first == e[i].first)
      s1.push(i);
    else
      g[++tot] = i;
    v[s.top()].push_back(i);
    v[i].push_back(s.top());
    s.push(i);
  }
  while (!s1.empty()) {
    g[++tot] = s1.top();
    s1.pop();
  }
  int head = 0, tail = 0;
  q[0] = tri(0, m + 1, 1);
  memset(pd, true, sizeof(pd));
  while (head <= tail) {
    int w = find(q[head].x, -1, q[head].y);
    find(w, -1, q[head].y);
    f[w] = q[head].z;
    head++;
    pd[w] = false;
    int t;
    for (int i = 0; i < v[w].size(); i++)
      if (pd[t = v[w][i]]) {
        q[++tail] = tri(t, sz[t], f[w] + 1);
      }
  }
  reverse(g + 1, g + tot + 1);
  for (int i = 1; i <= tot; i++) printf("%d ", f[g[i]]);
  puts("");
  return 0;
}
