#include <bits/stdc++.h>
using namespace std;
const int maxn = 100003;
vector<pair<int, int> > diagonals;
vector<int> regions[maxn];
int N, M;
bool comp(const pair<int, int> &s1, const pair<int, int> &s2) {
  int x = min(s1.second - s1.first - 1, N - 2 - (s1.second - s1.first - 1));
  int y = min(s2.second - s2.first - 1, N - 2 - (s2.second - s2.first - 1));
  return x < y;
}
map<pair<int, int>, int> MAP;
vector<int> G[maxn];
int T[maxn], mark[maxn];
void dfs(int nodo, int pad) {
  T[nodo] = 1;
  for (auto ady : G[nodo]) {
    if (ady == pad) continue;
    if (mark[ady]) continue;
    dfs(ady, nodo);
    T[nodo] += T[ady];
  }
}
int dfsc(int nodo, int pad, int cant) {
  for (auto ady : G[nodo]) {
    if (!mark[ady] && ady != pad && T[ady] >= cant / 2)
      return dfsc(ady, nodo, cant);
  }
  return nodo;
}
void centroid(int nodo, int pad, int lv) {
  dfs(nodo, pad);
  int centro = dfsc(nodo, pad, T[nodo]);
  mark[centro] = lv;
  for (auto i : G[centro]) {
    if (mark[i] || i == pad) continue;
    centroid(i, centro, lv + 1);
  }
}
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cin >> N >> M;
  int x, y;
  for (int i = 1; i <= M; i++) {
    cin >> x >> y;
    if (x > y) swap(x, y);
    diagonals.push_back(pair<int, int>(x, y));
  }
  sort(begin(diagonals), end(diagonals), comp);
  set<int> S;
  for (int i = 1; i <= N; i++) S.insert(i);
  int k = 0;
  for (auto d : diagonals) {
    k++;
    x = d.second - d.first - 1, y = N - 2 - (d.second - d.first - 1);
    if (x <= y) {
      regions[k].push_back(d.first);
      auto it = S.lower_bound(d.first + 1);
      while (*it != d.second) {
        regions[k].push_back(*it);
        it++;
      }
      regions[k].push_back(d.second);
      for (int j = 1; j < (int)regions[k].size() - 1; j++)
        S.erase(S.find(regions[k][j]));
    } else {
      regions[k].push_back(d.first);
      regions[k].push_back(d.second);
      auto it = S.lower_bound(d.second + 1);
      while (it != S.end()) {
        regions[k].push_back(*it);
        it++;
      }
      it = S.begin();
      while (*it != d.first) {
        regions[k].push_back(*it);
        it++;
      }
      for (int j = 2; j < (int)regions[k].size(); j++)
        S.erase(S.find(regions[k][j]));
      sort(regions[k].begin(), regions[k].end());
    }
    reverse(regions[k].begin(), regions[k].end());
  }
  auto it = S.begin();
  k++;
  while (it != S.end()) regions[k].push_back(*it), it++;
  S.clear();
  reverse(regions[k].begin(), regions[k].end());
  sort(regions + 1, regions + k + 1);
  for (int i = 1; i <= k; i++) {
    for (int j = 0; j < (int)regions[i].size() - 1; j++) {
      int x = regions[i][j], y = regions[i][j + 1];
      if (x > y) swap(x, y);
      if (MAP.find(pair<int, int>(x, y)) != MAP.end()) {
        G[MAP[pair<int, int>(x, y)]].push_back(i);
        G[i].push_back(MAP[pair<int, int>(x, y)]);
        MAP.erase(MAP.find(pair<int, int>(x, y)));
      } else {
        MAP[pair<int, int>(x, y)] = i;
      }
    }
    int y = regions[i][0], x = regions[i][regions[i].size() - 1];
    if (x > y) swap(x, y);
    if (MAP.find(pair<int, int>(x, y)) != MAP.end()) {
      G[MAP[pair<int, int>(x, y)]].push_back(i);
      G[i].push_back(MAP[pair<int, int>(x, y)]);
      MAP.erase(MAP.find(pair<int, int>(x, y)));
    } else {
      MAP[pair<int, int>(x, y)] = i;
    }
  }
  centroid(1, -1, 1);
  cout << mark[1];
  for (int i = 2; i <= k; i++) cout << " " << mark[i];
}
