#include <bits/stdc++.h>
using namespace std;
template <class T>
void debug(T a, T b) {
  ;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
namespace std {
template <class S, class T>
ostream& operator<<(ostream& out, const pair<S, T>& a) {
  out << '(' << a.first << ',' << a.second << ')';
  return out;
}
}  // namespace std
long long int readL() {
  long long int res;
  scanf("%I64d", &res);
  return res;
}
void printL(long long int res) { printf("%I64d", res); }
const int INF = 5e8;
int n, m;
vector<int> g[100005];
pair<int, int> mst2[100005];
pair<int, int> es[100005];
int idx[100005], rev[100005];
vector<int> g2[100005];
int res[100005];
bool cut[100005];
int size[100005], whole;
int gsize(int v, int p) {
  size[v] = 1;
  for (auto to : g2[v]) {
    if (cut[to] || to == p) continue;
    size[v] += gsize(to, v);
  }
  return size[v];
}
int root, cost;
void groot(int v, int p) {
  int C = whole - size[v];
  for (auto to : g2[v]) {
    if (cut[to] || to == p) continue;
    groot(to, v);
    chmax(C, size[to]);
  }
  if (cost > C) {
    cost = C;
    root = v;
  }
}
void dfs(int v, int rank) {
  whole = gsize(v, -1);
  cost = INF;
  groot(v, -1);
  v = root;
  res[v] = rank;
  if (whole == 1) return;
  cut[v] = 1;
  for (auto to : g2[v]) {
    if (cut[to]) continue;
    dfs(to, rank + 1);
  }
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < (m); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    if (a > b) swap(a, b);
    es[i] = {a, b};
  }
  es[m++] = {0, n - 1};
  sort(es, es + m, [&](pair<int, int> a, pair<int, int> b) {
    return a.second - a.first < b.second - b.first;
  });
  set<pair<pair<int, int>, int> > range;
  int cnt = 0;
  for (int i = 0; i < (m); ++i) {
    int a = es[i].first, b = es[i].second;
    auto it = range.lower_bound({{a, -1}, -1});
    pair<int, int> last = {-1, -1};
    while (it != range.end() && it->first.second <= b) {
      last = it->first;
      g[cnt].push_back(it->second);
      g[it->second].push_back(cnt);
      range.erase(it++);
    }
    if (last.second == b)
      mst2[cnt] = {last.first, b};
    else
      mst2[cnt] = {b - 1, b};
    range.insert({{a, b}, cnt});
    ++cnt;
  }
  for (int i = 0; i < (cnt); ++i)
    if (mst2[i].second > mst2[i].first) swap(mst2[i].first, mst2[i].second);
  for (int i = 0; i < (cnt); ++i) idx[i] = i;
  sort(idx, idx + cnt, [&](int a, int b) { return mst2[a] < mst2[b]; });
  for (int i = 0; i < (cnt); ++i) rev[idx[i]] = i;
  for (int i = 0; i < (cnt); ++i)
    for (auto to : g[i]) g2[rev[i]].push_back(rev[to]);
  dfs(0, 0);
  for (int i = 0; i < (cnt); ++i) printf("%d\n", res[i] + 1);
  return 0;
}
