#include <bits/stdc++.h>
using namespace std;
struct CentroidD {
  long long n, val_vis;
  vector<vector<long long> > adj;
  vector<long long> cparent, szt, vis, dist;
  vector<vector<long long> > cdTree;
  CentroidD() {}
  CentroidD(long long n) : n(n) {
    val_vis = 0;
    vis.resize(n, -1);
    dist.resize(n, 0);
    cparent.resize(n, -1);
    szt.resize(n, 0);
    adj.resize(n);
    cdTree.resize(n);
  }
  void addEdge(long long u, long long v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
    return;
  }
  long long dfs(long long u, long long p) {
    szt[u] = 1;
    vis[u] = val_vis;
    for (long long v : adj[u]) {
      if (v != p && cparent[v] == -1 && vis[v] != val_vis) szt[u] += dfs(v, u);
    }
    return szt[u];
  }
  void decompotition(long long u, long long p, long long sz, long long pc,
                     long long d) {
    for (long long v : adj[u]) {
      if (v != p && cparent[v] == -1 && (szt[v] << 1ll) > sz) {
        decompotition(v, u, sz, pc, d);
        return;
      }
    }
    dist[u] = d;
    cparent[u] = pc;
    if (pc != -2) {
      cdTree[u].push_back(pc);
      cdTree[pc].push_back(u);
    }
    for (long long v : adj[u]) {
      if (cparent[v] == -1) {
        dfs(v, -1);
        val_vis++;
        decompotition(v, -1, szt[v], u, d + 1);
      }
    }
  }
  void build(long long u) {
    dfs(u, -1);
    val_vis++;
    decompotition(u, -1, szt[u], -2, 1);
  }
};
const long long MX = 1e5 + 10;
multiset<long long> adj[MX];
vector<long long> bloq;
map<pair<long long, long long>, bool> used;
map<pair<long long, long long>, vector<long long> > ari;
void deleteEdge(long long u, long long v) {
  auto it = adj[u].find(v);
  adj[u].erase(it);
  it = adj[v].find(u);
  adj[v].erase(it);
  return;
}
void add(long long u, long long v, long long id) {
  auto it = used.find({u, v});
  if (it != used.end()) {
    ari[{u, v}].push_back(id);
  }
  return;
}
void update(long long u, long long v, long long id) {
  add(min(u, v), max(u, v), id);
  bloq.clear();
  while (u != v) {
    bloq.push_back(u);
    auto it = adj[u].begin();
    long long x = *it;
    add(min(u, x), max(u, x), id);
    deleteEdge(x, u);
    u = x;
  }
  bloq.push_back(v);
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout.precision(10);
  cout << fixed;
  long long n, m, x, y;
  cin >> n >> m;
  for (long long i = 1; i < n; i++) {
    adj[i].insert(i + 1);
    adj[i + 1].insert(i);
  }
  adj[1].insert(n);
  adj[n].insert(1);
  for (long long i = 0; i < m; i++) {
    cin >> x >> y;
    used[{min(x, y), max(x, y)}] = true;
    adj[x].insert(y);
    adj[y].insert(x);
    adj[x].insert(y);
    adj[y].insert(x);
  }
  if (m == 0) {
    cout << 1 << "\n";
    return 0;
  }
  long long id = 0;
  vector<pair<vector<long long>, long long> > ord;
  for (long long u = n; u >= 1; u--) {
    while (!adj[u].empty()) {
      auto it = adj[u].begin();
      long long v = *it;
      deleteEdge(u, v);
      update(u, v, id);
      ord.push_back({bloq, id});
      id++;
    }
  }
  sort(ord.begin(), ord.end());
  CentroidD G;
  G = CentroidD(id);
  for (auto xx : ari) {
    G.addEdge(xx.second[0], xx.second[1]);
  }
  G.build(0);
  for (long long i = 0; i < id; i++) {
    cout << G.dist[ord[i].second] << " ";
  }
  cout << "\n";
  return 0;
}
