#include <bits/stdc++.h>
int n, m, tot;
std::pair<int, int> diag[(100010)];
std::vector<int> vec[(100010)];
std::vector<int> node[(100010)];
int ans[(100010)], sz[(100010)];
bool vis[(100010)];
bool cmp(const std::pair<int, int> &A, const std::pair<int, int> &B) {
  int a = std::min(A.second - A.first - 1, (n - 2) - (A.second - A.first - 1));
  int b = std::min(B.second - B.first - 1, (n - 2) - (B.second - B.first - 1));
  return a < b;
}
void getroot(int u, int fa, int &root, int &rootsz, int nown) {
  sz[u] = 1;
  int maxsz = 0;
  for (auto v : vec[u]) {
    if (vis[v] || v == fa) continue;
    getroot(v, u, root, rootsz, nown);
    sz[u] += sz[v];
    maxsz = std::max(maxsz, sz[v]);
  }
  maxsz = std::max(maxsz, nown - sz[u]);
  if (rootsz > maxsz) {
    rootsz = maxsz;
    root = u;
  }
}
void getsz(int u, int fa) {
  sz[u] = 1;
  for (auto v : vec[u]) {
    if (vis[v] || v == fa) continue;
    getsz(v, u);
    sz[u] += sz[v];
  }
}
void solve(int u, int dep) {
  ans[u] = dep;
  vis[u] = true;
  getsz(u, 0);
  for (auto v : vec[u]) {
    if (!vis[v]) {
      int root = 0, rootsz = tot;
      getroot(v, u, root, rootsz, sz[v]);
      solve(root, dep + 1);
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &diag[i].first, &diag[i].second);
    if (diag[i].first > diag[i].second) {
      std::swap(diag[i].first, diag[i].second);
    }
  }
  std::sort(diag + 1, m + diag + 1, cmp);
  std::set<int> set;
  std::set<int>::iterator it;
  for (int i = 1; i <= n; ++i) {
    set.insert(i);
  }
  for (int i = 1; i <= m; ++i) {
    ++tot;
    if (diag[i].second - diag[i].first - 1 <
        (n - 2) - (diag[i].second - diag[i].first - 1)) {
      node[tot].push_back(diag[i].first);
      it = set.upper_bound(diag[i].first);
      while (*it != diag[i].second) {
        node[tot].push_back(*it);
        ++it;
      }
      node[tot].push_back(diag[i].second);
      for (int j = 1, sz = (int)(node[tot].size()); j < sz - 1; ++j) {
        set.erase(node[tot][j]);
      }
    } else {
      while (*set.begin() != diag[i].first) {
        node[tot].push_back(*set.begin());
        set.erase(set.begin());
      }
      node[tot].push_back(diag[i].first);
      node[tot].push_back(diag[i].second);
      int j = (int)(node[tot].size());
      it = set.upper_bound(diag[i].second);
      while (it != set.end()) {
        node[tot].push_back(*it);
        ++it;
      }
      for (int sz = (int)(node[tot].size()); j < sz; ++j) {
        set.erase(node[tot][j]);
      }
    }
    std::reverse(node[tot].begin(), node[tot].end());
  }
  ++tot;
  while ((int)(set.size()) != 0) {
    node[tot].push_back(*set.begin());
    set.erase(set.begin());
  }
  std::reverse(node[tot].begin(), node[tot].end());
  std::sort(node + 1, tot + node + 1);
  std::map<std::pair<int, int>, int> map;
  for (int i = 1; i <= tot; ++i) {
    for (int j = 0, sz = (int)(node[i].size()); j < sz - 1; ++j) {
      if (node[i][j] == node[i][j + 1] + 1) {
        continue;
      }
      if (map.find(std::make_pair(node[i][j], node[i][j + 1])) != map.end()) {
        int v = map[std::make_pair(node[i][j], node[i][j + 1])];
        vec[v].push_back(i);
        vec[i].push_back(v);
        map.erase(std::make_pair(node[i][j], node[i][j + 1]));
      } else {
        map[std::make_pair(node[i][j], node[i][j + 1])] = i;
      }
    }
    int j = (int)(node[i].size()) - 1;
    if (!(node[i][0] == n && node[i][j] == 1)) {
      if (map.find(std::make_pair(node[i][0], node[i][j])) != map.end()) {
        int v = map[std::make_pair(node[i][0], node[i][j])];
        vec[v].push_back(i);
        vec[i].push_back(v);
        map.erase(std::make_pair(node[i][0], node[i][j]));
      } else {
        map[std::make_pair(node[i][0], node[i][j])] = i;
      }
    }
  }
  int root = 0, rootsz = tot;
  getroot(1, 0, root, rootsz, tot);
  solve(root, 1);
  for (int i = 1; i <= tot; ++i) {
    printf("%d%c", ans[i], " \n"[i == tot]);
  }
  return 0;
}
