#include <bits/stdc++.h>
using namespace std;
inline void check_max(int& a, int b) {
  if (a < b) a = b;
}
const int MAX_N = 100100;
int n, m;
vector<int> ed[MAX_N];
int color[MAX_N];
bool valid[MAX_N];
int centroid(int rt) {
  static int que[MAX_N];
  static int par[MAX_N];
  int f = 0, b = 0;
  que[b++] = rt;
  par[rt] = 0;
  while (f < b) {
    int u = que[f++];
    for (int v : ed[u]) {
      if (!valid[v] || v == par[u]) continue;
      que[b++] = v;
      par[v] = u;
    }
  }
  static int sz[MAX_N];
  static int ms[MAX_N];
  rt = -1;
  for (int i = b - 1; i >= 0; --i) {
    int u = que[i];
    sz[u] = 1;
    ms[u] = 0;
    for (int v : ed[u]) {
      if (!valid[v] || v == par[u]) continue;
      sz[u] += sz[v];
      check_max(ms[u], sz[v]);
    }
    check_max(ms[u], b - sz[u]);
    if (rt == -1 || ms[u] < ms[rt]) rt = u;
  }
  return rt;
}
void dfs(int u, int c) {
  u = centroid(u);
  valid[u] = false;
  color[u] = c;
  for (int v : ed[u]) {
    if (!valid[v]) continue;
    dfs(v, c + 1);
  }
}
vector<pair<int, int>> es;
map<int, int> go[MAX_N];
void build(int l, int r, int u) {
  for (int ll = l; ll < r; ++ll) {
    if (go[ll].empty()) continue;
    auto it = prev(go[ll].end());
    int rr = it->first, v = it->second;
    go[ll].erase(it);
    ed[u].push_back(v);
    ed[v].push_back(u);
    build(ll, rr, v);
    ll = rr - 1;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  int a, b;
  es.emplace_back(1, n);
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &a, &b);
    if (a > b) swap(a, b);
    es.emplace_back(a, b);
  }
  sort(es.begin(), es.end(),
       [](const pair<int, int>& a, const pair<int, int>& b) {
         return a.second == b.second ? a.first < b.first : a.second < b.second;
       });
  int idx = 0, rt;
  for (const auto& pr : es) {
    go[pr.first][pr.second] = ++idx;
    if (pr == make_pair(1, n)) rt = idx;
  }
  go[1].erase(n);
  build(1, n, rt);
  fill(valid, valid + m + 2, true);
  dfs(1, 1);
  for (int i = 1; i <= m + 1; ++i) {
    printf("%d%c", color[i], " \n"[i == m + 1]);
  }
  return 0;
}
