#include <bits/stdc++.h>
using namespace std;
#pragma warning(disable : 4996)
const int N = 1e5 + 5;
int col[N], sz[N];
set<pair<int, int>> d[N];
vector<int> d2[N], g[N];
map<vector<int>, int> mp;
int n, m;
int f(int a, int b = n) {
  if (a < 0) a += b;
  if (a >= b) a -= b;
  return a;
}
void dfs(int node, int anc = -1) {
  sz[node] = 1;
  for (int to : g[node]) {
    if (to != anc && !col[to]) {
      dfs(to, node);
      sz[node] += sz[to];
    }
  }
}
int findCentroid(int node, int half, int anc = -1) {
  for (int to : g[node]) {
    if (!col[to] && to != anc && sz[to] > half)
      return findCentroid(to, half, node);
  }
  return node;
}
void solve(int node, int h = 1) {
  dfs(node);
  node = findCentroid(node, sz[node] / 2);
  col[node] = h;
  for (int to : g[node]) {
    if (!col[to]) solve(to, h + 1);
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  if (m == 0) {
    cout << 1;
    return 0;
  }
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    d2[a].push_back(b);
    d2[b].push_back(a);
    d[a].insert({f(b - a), b});
    d[b].insert({f(a - b), a});
  }
  for (int i = 0; i < n; i++) {
    d[i].insert({1, f(i + 1)});
    d[i].insert({n - 1, f(i - 1)});
    d2[i].push_back(f(i - 1));
    d2[i].push_back(f(i + 1));
  }
  vector<vector<int>> faces;
  for (int i = 0; i < n; i++) {
    while (!d[i].empty()) {
      int x = i, y = d[i].begin()->second;
      vector<int> fc;
      set<pair<int, int>> used = {*d[i].begin()};
      while (true) {
        fc.push_back(y);
        auto it = d[y].upper_bound({f(x - y), x});
        if (it == d[y].end()) it = d[y].begin();
        if (used.count(*it)) break;
        x = y;
        y = it->second;
        used.insert(*it);
      }
      for (int j = 0; j < fc.size(); j++) {
        int k = j == fc.size() - 1 ? 0 : j + 1;
        d[fc[j]].erase({f(fc[k] - fc[j]), fc[k]});
      }
      if (fc.size() == n) continue;
      sort(fc.rbegin(), fc.rend());
      faces.push_back(fc);
    }
  }
  sort(faces.begin(), faces.end());
  for (int i = 0; i < faces.size(); i++) {
    for (int j = 0; j < faces[i].size(); j++) {
      vector<int> v;
      for (int k = 0; k < 3; k++) {
        v.push_back({faces[i][f(j + k, faces[i].size())]});
      }
      mp[v] = i;
    }
  }
  for (int i = 0; i < n; i++) {
    sort(d2[i].begin(), d2[i].end(),
         [&](int x, int y) { return f(x - i) < f(y - i); });
    for (int j = 1; j < (int)d2[i].size() - 1; j++) {
      int x = mp[{d2[i][j - 1], i, d2[i][j]}],
          y = mp[{d2[i][j], i, d2[i][j + 1]}];
      g[x].push_back(y);
    }
  }
  solve(0);
  for (int i = 0; i < faces.size(); i++) cout << col[i] << " ";
  return 0;
}
