#include <bits/stdc++.h>
template <typename T>
void MACRO_VAR_Scan(T& t) {
  std::cin >> t;
}
template <typename First, typename... Rest>
void MACRO_VAR_Scan(First& first, Rest&... rest) {
  std::cin >> first;
  MACRO_VAR_Scan(rest...);
}
template <typename T>
void MACRO_VEC_ROW_Init(int n, T& t) {
  t.resize(n);
}
template <typename First, typename... Rest>
void MACRO_VEC_ROW_Init(int n, First& first, Rest&... rest) {
  first.resize(n);
  MACRO_VEC_ROW_Init(n, rest...);
}
template <typename T>
void MACRO_VEC_ROW_Scan(int p, T& t) {
  std::cin >> t[p];
}
template <typename First, typename... Rest>
void MACRO_VEC_ROW_Scan(int p, First& first, Rest&... rest) {
  std::cin >> first[p];
  MACRO_VEC_ROW_Scan(p, rest...);
}
template <typename T>
inline T CHMAX(T& a, const T b) {
  return a = (a < b) ? b : a;
}
template <typename T>
inline T CHMIN(T& a, const T b) {
  return a = (a > b) ? b : a;
}
void CHECKTIME(std::function<void()> f) {
  auto start = std::chrono::system_clock::now();
  f();
  auto end = std::chrono::system_clock::now();
  auto res = std::chrono::duration_cast<std::chrono::nanoseconds>((end - start))
                 .count();
  std::cerr << "[Time:" << res << "ns  (" << res / (1.0e9) << "s)]\n";
}
using ll = long long;
using ull = unsigned long long;
constexpr ll INFINT = 1 << 30;
constexpr ll INFINT_LIM = (1LL << 31) - 1;
constexpr ll INFLL = 1LL << 60;
constexpr ll INFLL_LIM = (1LL << 62) - 1 + (1LL << 62);
constexpr double EPS = 1e-7;
constexpr ll MOD = 1000000007;
constexpr double PI = 3.141592653589793238462643383279;
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  ;
  ll n, m;
  MACRO_VAR_Scan(n, m);
  ;
  std::vector<ll> a, b;
  MACRO_VEC_ROW_Init(m, a, b);
  for (ll i = 0; i < m; ++i) {
    MACRO_VEC_ROW_Scan(i, a, b);
  };
  std::vector<std::vector<ll>> g(m + 1);
  std::vector<std::pair<std::vector<ll>, ll>> dat(m + 1);
  std::vector<std::pair<ll, ll>> pv(m + 1);
  for (ll i = 0; i < ll(m); ++i) {
    --a[i];
    --b[i];
    if (a[i] > b[i]) std::swap(a[i], b[i]);
    pv[i] = std::pair<ll, ll>(b[i] - a[i], a[i]);
  }
  pv[m] = std::pair<ll, ll>(n - 1, 0);
  std::sort((pv).begin(), (pv).end());
  std::set<ll> set;
  for (ll i = 0; i < ll(n); ++i) set.insert(i);
  for (ll i = 0; i < ll(m + 1); ++i) {
    ll from = pv[i].second;
    ll to = pv[i].first + pv[i].second;
    std::vector<ll> v;
    auto it = set.find(from), end = set.find(to);
    for (; it != end; ++it) {
      v.emplace_back(*it);
    }
    v.emplace_back(to);
    it = std::next(set.find(from));
    set.erase(it, end);
    for (ll j = 0; j < ll(v.size() - 1); ++j) {
      if (v[j + 1] - v[j] > 1) {
        auto tt(std::pair<ll, ll>(v[j + 1] - v[j], v[j]));
        ll next = std::lower_bound((pv).begin(), (pv).end(), tt) - pv.begin();
        g[i].emplace_back(next);
        g[next].emplace_back(i);
      }
    }
    std::sort((v).begin(), (v).end());
    std::reverse((v).begin(), (v).end());
    v.resize(2);
    dat[i] = std::make_pair(v, i);
  }
  std::sort((dat).begin(), (dat).end());
  std::vector<bool> used(m + 1, false);
  std::vector<ll> subtreeSize(m + 1, 0);
  std::function<ll(ll, ll)> calcSubtreeSize = [&](ll v, ll par) {
    ll res = 1;
    for (const auto& to : g[v]) {
      if (to == par || used[to]) continue;
      res += calcSubtreeSize(to, v);
    }
    return subtreeSize[v] = res;
  };
  std::function<std::pair<ll, ll>(ll, ll, ll)> getCentroid = [&](ll v, ll par,
                                                                 ll size) {
    std::pair<ll, ll> res = std::make_pair(INFINT, -1);
    ll s = 1, m = 0;
    for (const auto& to : g[v]) {
      if (to == par || used[to]) continue;
      res = std::min(res, getCentroid(to, v, size));
      m = std::max(m, subtreeSize[to]);
      s += subtreeSize[to];
    }
    m = std::max(m, size - s);
    res = std::min(res, std::make_pair(m, v));
    return res;
  };
  std::vector<ll> ans(m + 1);
  std::function<void(ll, ll)> solve = [&](ll v, ll c) {
    ll s = calcSubtreeSize(v, -1);
    auto p = getCentroid(v, -1, s);
    used[p.second] = true;
    ans[p.second] = c;
    for (const auto& next : g[p.second]) {
      if (used[next]) continue;
      solve(next, c + 1);
    }
  };
  solve(0, 1);
  for (ll i = 0; i < ll(g.size()); ++i) {
    std::cout << ans[dat[i].second];
    std::cout << " ";
    ;
  }
  std::cout << "\n";
  ;
  return 0;
}
