#include <bits/stdc++.h>
using namespace std;
vector<int> regions[100010];
vector<int> ed[100010];
int n;
struct data {
  int a, b;
} diag[100010];
int sz[100010];
bool done[100010];
int Ch[100010];
void dfs(int n, int p) {
  sz[n] = 1;
  for (int i = 0; i < ed[n].size(); i++) {
    int v = ed[n][i];
    if (v != p && done[v] == false) {
      dfs(v, n);
      sz[n] += sz[v];
    }
  }
}
int decompose(int cen, int ch) {
  dfs(cen, -1);
  int target = sz[cen] / 2, p = -1;
  bool ok = false;
  while (!ok) {
    ok = true;
    for (int i = 0; i < ed[cen].size(); i++) {
      int v = ed[cen][i];
      if (p != v && done[v] == false && sz[v] > target) {
        ok = false;
        p = cen;
        cen = v;
      }
    }
  }
  Ch[cen] = ch;
  done[cen] = true;
  for (int i = 0; i < ed[cen].size(); i++) {
    int v = ed[cen][i];
    if (!done[v]) {
      decompose(v, ch + 1);
    }
  }
  return cen;
}
bool comp(data l, data r) {
  int x = min(l.b - l.a - 1, n - 2 - l.b + l.a + 1);
  int y = min(r.b - r.a - 1, n - 2 - r.b + r.a + 1);
  return x < y;
}
int main() {
  int cs, ts, i, j, k, x, y, z, ans, q, m;
  scanf("%d", &n);
  scanf("%d", &m);
  for (i = 1; i <= m; i++) {
    scanf("%d", &x);
    scanf("%d", &y);
    if (x > y) swap(x, y);
    diag[i].a = x;
    diag[i].b = y;
  }
  sort(diag + 1, diag + m + 1, comp);
  set<int> st;
  for (i = 1; i <= n; i++) st.insert(i);
  int regsz = 0;
  vector<int> del;
  for (i = 1; i <= m; i++) {
    x = diag[i].b - diag[i].a - 1;
    y = n - 2 - x;
    if (x <= y) {
      regions[++regsz].push_back(diag[i].a);
      set<int>::iterator sit = st.upper_bound(diag[i].a);
      while (*sit != diag[i].b) {
        regions[regsz].push_back(*sit);
        del.push_back(*sit);
        sit++;
      }
      regions[regsz].push_back(diag[i].b);
    } else {
      set<int>::iterator sit = st.begin();
      regsz++;
      while (*sit != diag[i].a) {
        regions[regsz].push_back(*sit);
        del.push_back(*sit);
        sit++;
      }
      regions[regsz].push_back(diag[i].a);
      regions[regsz].push_back(diag[i].b);
      sit = st.upper_bound(diag[i].b);
      while (sit != st.end()) {
        regions[regsz].push_back(*sit);
        del.push_back(*sit);
        sit++;
      }
    }
    for (j = 0; j < del.size(); j++) st.erase(del[j]);
    del.clear();
    sort(regions[regsz].begin(), regions[regsz].end(), greater<int>());
  }
  if (st.size() != 0) {
    regsz++;
    while (st.size() != 0) {
      regions[regsz].push_back(*st.begin());
      st.erase(st.begin());
    }
    sort(regions[regsz].begin(), regions[regsz].end(), greater<int>());
  }
  sort(regions + 1, regions + regsz + 1);
  map<pair<int, int>, int> mp;
  for (i = 1; i <= regsz; i++) {
    for (j = 0; j < regions[i].size(); j++) {
      x = regions[i][j];
      if (j == regions[i].size() - 1)
        y = regions[i][0];
      else
        y = regions[i][j + 1];
      if (x < y) swap(x, y);
      if (x == y + 1) continue;
      if (mp.count(pair<int, int>(x, y)) == 0) {
        mp[pair<int, int>(x, y)] = i;
      } else {
        ed[i].push_back(mp[pair<int, int>(x, y)]);
        ed[mp[pair<int, int>(x, y)]].push_back(i);
      }
    }
  }
  decompose(1, 1);
  for (i = 1; i <= regsz; i++) {
    if (i != 1) printf(" ");
    printf("%d", Ch[i]);
  }
  printf("\n");
  return 0;
}
