#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 11;
typedef int i_N[maxN];
int N, M, C;
vector<int> tree[maxN];
set<int> adj[maxN];
pair<int, int> edge[maxN];
map<pair<int, pair<int, int> >, int> mp;
map<pair<int, int>, pair<int, pair<int, int> > > regId;
map<pair<int, int>, int> ban;
vector<pair<int, pair<int, int> > > reg;
i_N P, Cchild, level, del;
int tmp = 0;
void dfs(int u) {
  Cchild[u] = 1;
  for (int i = 0; i < (int)tree[u].size(); i++) {
    int v = tree[u][i];
    if (P[v]) continue;
    P[v] = u;
    dfs(v);
    Cchild[u] += Cchild[v];
  }
}
int notCentroid(int u, int N) {
  int tmp = 0;
  for (int i = 0; i < (int)tree[u].size(); i++) {
    int v = tree[u][i];
    if (P[v] != u || del[v]) continue;
    if (Cchild[v] > N / 2) return v;
    tmp += Cchild[v];
  }
  return N - tmp - 1 > N / 2 ? P[u] : 0;
}
void findCentroid(int st, int N, int lv) {
  int u = st, v;
  while ((v = notCentroid(u, N))) u = v;
  del[u] = 1;
  level[u] = lv;
  for (v = P[u]; v != -1 && !del[v]; v = P[v]) Cchild[v] -= Cchild[u];
  int tmp = 0;
  for (int i = 0; i < (int)tree[u].size(); i++) {
    int v = tree[u][i];
    if (P[v] != u || del[v]) continue;
    tmp += Cchild[v];
    findCentroid(v, Cchild[v], lv + 1);
  }
  if (P[u] != -1 && !del[P[u]]) findCentroid(P[u], N - tmp - 1, lv + 1);
}
bool bfs(int st, int en, pair<int, pair<int, int> > &reg) {
  vector<int> path;
  for (int u = st, v; u != en; u = v) {
    path.push_back(u);
    set<int>::iterator it;
    if (st < en) {
      if (u == st)
        it = adj[u].lower_bound(en);
      else
        it = adj[u].upper_bound(en);
      it--;
      v = *it;
      if (ban[pair<int, int>(u, v)]) return false;
    } else {
      if (u == st)
        it = adj[u].lower_bound(en);
      else
        it = adj[u].upper_bound(en);
      if (it == adj[u].begin()) it = adj[u].end();
      it--;
      v = *it;
      if (ban[pair<int, int>(u, v)]) return false;
    }
  }
  path.push_back(en);
  vector<int> tmp = path;
  sort(tmp.begin(), tmp.end(), greater<int>());
  reg = pair<int, pair<int, int> >(tmp[0], pair<int, int>(tmp[1], tmp[2]));
  for (int i = 1; i < (int)path.size(); i++) {
    regId[pair<int, int>(path[i - 1], path[i])] = reg;
    ban[pair<int, int>(path[i - 1], path[i])] = 1;
  }
  regId[pair<int, int>(path.back(), path[0])] = reg;
  ban[pair<int, int>(path.back(), path[0])] = 1;
  return true;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> N >> M;
  for (int i = 1; i <= M; i++) {
    int u, v;
    cin >> u >> v;
    edge[i] = pair<int, int>(u, v);
    adj[u].insert(v);
    adj[v].insert(u);
  }
  for (int i = 1; i <= N; i++) {
    adj[i].insert(i == N ? 1 : i + 1);
    adj[i == N ? 1 : i + 1].insert(i);
  }
  C = M + 1;
  for (int i = 1; i <= M; i++) {
    int u = edge[i].first, v = edge[i].second;
    if (u > v) swap(u, v);
    pair<int, pair<int, int> > r;
    if (bfs(u, v, r)) reg.push_back(r);
    if (bfs(v, u, r)) reg.push_back(r);
  }
  sort(reg.begin(), reg.end());
  reg.resize(unique(reg.begin(), reg.end()) - reg.begin());
  for (int i = 1; i <= M; i++) {
    int u = edge[i].first, v = edge[i].second;
    int id1 = lower_bound(reg.begin(), reg.end(), regId[pair<int, int>(u, v)]) -
              reg.begin() + 1;
    int id2 = lower_bound(reg.begin(), reg.end(), regId[pair<int, int>(v, u)]) -
              reg.begin() + 1;
    tree[id1].push_back(id2);
    tree[id2].push_back(id1);
  }
  P[1] = -1;
  dfs(1);
  findCentroid(1, M + 1, 1);
  for (int u = 1; u <= M + 1; u++) cout << level[u] << ' ';
}
