#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int n, m, color[N], valid[N], rt, cnt;
vector<int> ed[N];
inline void read(int &x) {
  char c = getchar();
  x = 0;
  while (c > '9' || c < '0') c = getchar();
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
}
inline bool cmp(pair<int, int> a, pair<int, int> b) {
  return a.second == b.second ? a.first < b.first : a.second < b.second;
}
int find(int rt) {
  static int q[N], par[N];
  int l = 0, r = 0;
  q[r++] = rt;
  par[rt] = 0;
  while (l < r) {
    int u = q[l++];
    for (unsigned i = 0; i < ed[u].size(); ++i) {
      int v = ed[u][i];
      if (!valid[v] || v == par[u]) continue;
      q[r++] = v;
      par[v] = u;
    }
  }
  static int sz[N], ms[N];
  rt = -1;
  for (int i = r - 1; i >= 0; --i) {
    int u = q[i];
    sz[u] = 1;
    ms[u] = 0;
    for (unsigned j = 0; j < ed[u].size(); ++j) {
      int v = ed[u][j];
      if (!valid[v] || v == par[u]) continue;
      sz[u] += sz[v];
      ms[u] = max(ms[u], sz[v]);
    }
    ms[u] = max(ms[u], r - sz[u]);
    if (rt == -1 || ms[u] < ms[rt]) rt = u;
  }
  return rt;
}
void dfs(int u, int c) {
  u = find(u);
  valid[u] = false;
  color[u] = c;
  for (unsigned i = 0; i < ed[u].size(); ++i) {
    int v = ed[u][i];
    if (!valid[v]) continue;
    dfs(v, c + 1);
  }
}
vector<pair<int, int>> a;
map<int, int> mp[N];
void build(int l, int r, int u) {
  for (int L = l; L < r; ++L) {
    if (mp[L].empty()) continue;
    auto it = prev(mp[L].end());
    int R = it->first, v = it->second;
    mp[L].erase(it);
    ed[u].push_back(v);
    ed[v].push_back(u);
    build(L, R, v);
    L = R - 1;
  }
}
int main() {
  read(n);
  read(m);
  a.emplace_back(1, n);
  for (int i = 0; i < m; ++i) {
    int x, y;
    read(x);
    read(y);
    if (x > y) swap(x, y);
    a.emplace_back(x, y);
  }
  sort(a.begin(), a.end(), cmp);
  for (unsigned i = 0; i < a.size(); ++i) {
    pair<int, int> kkk = a[i];
    mp[kkk.first][kkk.second] = ++cnt;
    if (kkk == make_pair(1, n)) rt = cnt;
  }
  mp[1].erase(n);
  build(1, n, rt);
  fill(valid, valid + m + 2, 1);
  dfs(1, 1);
  for (int i = 1; i <= m + 1; ++i) printf("%d ", color[i]);
  return 0;
}
