#include <bits/stdc++.h>
using namespace std;
const int mx = 1e5 + 10;
vector<int> g[mx], t[mx];
int p[mx];
bool vis[mx];
int color[mx];
int sz[mx];
struct iv {
  int l, r, i;
  bool operator<(iv a) const { return r <= a.l; }
};
int centroid;
int all;
void dfs(int u, int pu) {
  sz[u] = 1;
  p[u] = pu;
  bool ok = true;
  for (int v : t[u])
    if (v != pu && color[v] == 0) {
      dfs(v, u);
      sz[u] += sz[v];
      if (sz[v] + sz[v] > all) ok = false;
    }
  int sp = all - sz[u];
  if (sp + sp > all) ok = false;
  if (ok) centroid = u;
}
void solve(int u, int col) {
  dfs(u, u);
  color[centroid] = col++;
  sz[p[centroid]] = all - sz[centroid];
  vector<pair<int, int> > children;
  for (int v : t[centroid])
    if (color[v] == 0) {
      children.push_back(make_pair(v, sz[v]));
    }
  for (auto v : children) {
    all = v.second;
    solve(v.first, col);
  }
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    --u, --v;
    if (u > v) swap(u, v);
    g[v].push_back(u);
  }
  set<iv> s;
  int cmp = 0;
  memset(p, -1, sizeof p);
  int last = -1;
  for (int i = 0; i < n; i++) {
    sort(g[i].begin(), g[i].end(), greater<int>());
    int id = cmp + g[i].size() - 1;
    if (i == n - 1) {
      id++;
      last = cmp;
    }
    for (int j : g[i]) {
      while (true) {
        auto it = s.lower_bound({j, i});
        if (it != s.end() && j <= it->l && it->r <= i) {
          p[it->i] = id;
          s.erase(it);
        } else
          break;
      }
      s.insert({j, i, id--});
    }
    cmp += g[i].size();
    if (i == n - 1) cmp++;
  }
  if (last == -1) last = cmp++;
  for (auto x : s) {
    p[x.i] = last;
  }
  for (int i = 0; i < cmp; i++)
    if (p[i] != -1) {
      t[p[i]].push_back(i);
      t[i].push_back(p[i]);
    }
  all = cmp;
  solve(0, 1);
  for (int i = 0; i < cmp; i++) printf("%d ", color[i]);
  puts("");
  return 0;
}
