#include <bits/stdc++.h>
using namespace std;
const int N = int(1e6) + 10;
vector<int> g[N], tree[N], V[N];
map<pair<int, int>, vector<int>> E;
int origin, n;
int vis[N], C[N], R[N];
bool cmp(int a, int b) {
  if (a < origin) a = a + n;
  if (b < origin) b = b + n;
  return a < b;
}
bool cmp1(int a, int b) { return V[a] < V[b]; }
namespace Centroid {
vector<int> g[N];
int sub[N], nn, U[N], V[N], done[N], m;
int adj(int u, int e) { return U[e] ^ V[e] ^ u; }
void dfs1(int u, int p) {
  sub[u] = 1;
  nn++;
  for (auto e : g[u]) {
    int w = adj(u, e);
    if (w != p && !done[e]) dfs1(w, u), sub[u] += sub[w];
  }
}
int dfs2(int u, int p) {
  for (auto e : g[u]) {
    if (done[e]) continue;
    int w = adj(u, e);
    if (w != p && sub[w] > nn / 2) return dfs2(w, u);
  }
  return u;
}
void decompose(int root, int p, int l = 1) {
  nn = 0;
  dfs1(root, root);
  root = dfs2(root, root);
  if (p == -1) p = root;
  C[root] = l;
  for (auto e : g[root]) {
    if (done[e]) continue;
    done[e] = 1;
    int w = adj(root, e);
    decompose(w, root, l + 1);
  }
}
void addEdge(int a, int b) {
  m++;
  U[m] = a;
  V[m] = b;
  g[a].push_back(m);
  g[b].push_back(m);
}
}  // namespace Centroid
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    g[i].push_back((i + 1) % n);
    g[(i + 1) % n].push_back(i);
    ;
  }
  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d", &a);
    scanf("%d", &b);
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
    ;
  }
  for (int i = 0; i < n; i++) {
    origin = i;
    sort(g[i].begin(), g[i].end(), cmp);
  }
  map<pair<int, int>, int> mp;
  vector<vector<int>> A;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < (int)(g[i].size()) - 1; j++) {
      int a = g[i][j], b = g[i][j + 1];
      A.push_back({a, i, b});
      mp[make_pair(a, i)] = b;
    }
  }
  map<vector<int>, int> vis1;
  int cr = 0;
  for (auto angle : A) {
    if (vis1[angle]) continue;
    int a = angle[0], b = angle[1], c = angle[2];
    ++cr;
    int cv = b;
    while (!vis[cv]) {
      V[cr].push_back(cv);
      E[make_pair(min(a, b), max(a, b))].push_back(cr);
      vis[cv] = 1;
      vis1[{a, b, c}] = 1;
      cv = mp[make_pair(b, c)];
      a = b;
      b = c;
      c = cv;
      cv = b;
    }
    sort(V[cr].begin(), V[cr].end());
    reverse(V[cr].begin(), V[cr].end());
    for (auto x : V[cr]) vis[x] = 0;
  }
  n = cr;
  for (int i = 1; i <= n; i++) R[i] = i;
  sort(R + 1, R + 1 + n, cmp1);
  for (auto e : E) {
    assert((int)(e.second.size()) <= 2);
    if ((int)(e.second.size()) == 1) continue;
    int a = e.second[0], b = e.second[1];
    Centroid::addEdge(a, b);
  }
  Centroid::decompose(1, -1);
  for (int i = 1; i <= n; i++) printf("%d ", C[R[i]]);
  puts("");
  return 0;
}
