#include <bits/stdc++.h>
using namespace std;
long long ksm(long long a, long long b) {
  if (!b) return 1;
  long long ns = ksm(a, b >> 1);
  ns = ns * ns % 998244353;
  if (b & 1) ns = ns * a % 998244353;
  return ns;
}
set<int> eg[200005];
vector<int> mx[200005];
int fl[200005];
int col[200005];
int idcnt = 0;
void ins(int id, int num) {
  if (mx[id].size() >= 3) return;
  mx[id].push_back(num);
}
struct edge {
  int u, v, fl;
  edge *next;
  edge *rev;
} p[200005 << 1], *h[200005];
int egcnt = 0;
void ade(int u, int v) {
  edge *n1 = &p[egcnt++];
  edge *n2 = &p[egcnt++];
  n1->u = u, n1->v = v, n1->fl = 1;
  n2->u = v, n2->v = u, n2->fl = 1;
  n1->rev = n2, n2->rev = n1;
  n1->next = h[u], h[u] = n1;
  n2->next = h[v], h[v] = n2;
}
int work(int l, int r) {
  if (l == r) {
    idcnt++;
    mx[idcnt].push_back(l);
    return idcnt;
  }
  vector<pair<int, int> > cur;
  cur.push_back(make_pair(l + 1, 1)), cur.push_back(make_pair(r, 1));
  set<int>::iterator g = eg[l].lower_bound(l);
  while (g != eg[l].end() && (*g) <= r) {
    cur.push_back(make_pair(*g, 0));
    g++;
  }
  sort(cur.begin(), cur.end());
  vector<int> id(cur.size());
  int rr = 0;
  for (int i = 0; i < cur.size() - 1; i++) {
    int j = work(cur[i].first, cur[i + 1].first);
    if (!fl[j]) {
      ins(j, l);
      if (cur[i + 1].second == 0)
        fl[j] = 1;
      else
        rr = j;
      id[i] = j;
    }
    if (i >= 1) ade(id[i], id[i - 1]);
  }
  return rr;
}
bool cmp2(int a, int b) {
  for (int j = 0; j < 3; j++)
    if (mx[a][j] != mx[b][j]) return mx[a][j] < mx[b][j];
  return 0;
}
int mxsz;
int ns, nans;
int sz[200005], dep[200005];
vector<int> td[200005], tf[200005];
void dfs(int a, int fa, int tp) {
  sz[a] = 1;
  int mr = 0;
  for (edge *p = h[a]; p; p = p->next) {
    if (!p->fl) continue;
    if (p->v == fa) continue;
    dep[p->v] = dep[a] + 1, dfs(p->v, a, tp);
    mr = max(mr, sz[p->v]);
    sz[a] += sz[p->v];
  }
  if (tp) {
    int ra = max(mr, mxsz - sz[a]);
    if (ra < nans) nans = ra, ns = a;
  }
}
void wo(int a, int rs) {
  col[a] = rs;
  dep[a] = 0, dfs(a, -1, 0);
  for (edge *p = h[a]; p; p = p->next) {
    if (!p->fl) continue;
    p->fl = p->rev->fl = 0;
    nans = 200005, mxsz = sz[p->v];
    dfs(p->v, -1, 1);
    wo(ns, rs + 1);
  }
}
int main() {
  const int test = 0;
  int n, m;
  if (test)
    n = 100000, m = 99997;
  else
    cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    if (test)
      u = 1, v = i + 2;
    else
      scanf("%d%d", &u, &v);
    eg[u].insert(v), eg[v].insert(u);
  }
  work(1, n);
  wo(1, 1);
  vector<int> cur;
  for (int i = 1; i <= idcnt; i++) cur.push_back(i);
  sort(cur.begin(), cur.end(), cmp2);
  for (int i = 0; i < cur.size(); i++) printf("%d ", col[cur[i]]);
  return 0;
}
