#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void next_int(T &x) {
  x = 0;
  char c;
  bool neg = false;
  while (!isdigit(c = getchar()))
    if (c == '-') neg = true;
  do x = x * 10 + c - 48;
  while (isdigit(c = getchar()));
  if (neg) x = -x;
}
template <typename T>
inline void write_int(T x, char last = 0) {
  if (x < 0) putchar('-'), x = abs(x);
  char tmp[20];
  int cnt = 0;
  while (x >= 10) tmp[cnt++] = x % 10 + 48, x /= 10;
  tmp[cnt] = x + 48;
  for (int i = (cnt); i >= (0); --i) putchar(tmp[i]);
  if (last) putchar(last);
}
const int N = (int)1e5 + 5;
int n, m, k, sz[N], n2, ans[N];
bool vis[N];
vector<pair<int, int> > e;
set<int> s;
vector<int> nodes[N], g[N];
bool cmp(pair<int, int> &x, pair<int, int> &y) {
  int xx = min(x.second - x.first - 1, n - x.second + x.first - 1);
  int yy = min(y.second - y.first - 1, n - y.second + y.first - 1);
  return xx < yy;
}
void dfs_sz(int u, int p) {
  sz[u] = 1, ++n2;
  for (int i = (0); i < (((int)g[u].size())); ++i) {
    int v = g[u][i];
    if (v == p || vis[v]) continue;
    dfs_sz(v, u);
    sz[u] += sz[v];
  }
}
int dfs_mid(int u, int p) {
  for (int i = (0); i < (((int)g[u].size())); ++i) {
    int v = g[u][i];
    if (v == p || vis[v]) continue;
    if (sz[v] > n2 / 2) return dfs_mid(v, u);
  }
  return u;
}
void coloring(int u, int level) {
  n2 = 0;
  dfs_sz(u, 0);
  int mid = dfs_mid(u, 0);
  vis[mid] = true, ans[mid] = level + 1;
  for (int i = (0); i < (((int)g[mid].size())); ++i) {
    int v = g[mid][i];
    if (vis[v]) continue;
    coloring(v, level + 1);
  }
}
int main() {
  next_int(n), next_int(m);
  for (int i = (1); i <= (m); ++i) {
    int u, v;
    next_int(u), next_int(v);
    e.push_back(pair<int, int>(min(u, v), max(u, v)));
  }
  sort(e.begin(), e.end(), cmp);
  for (int i = (1); i <= (n); ++i) s.insert(i);
  for (int i = (0); i < (m); ++i) {
    pair<int, int> &tmp = e[i];
    ++k;
    if (tmp.second - tmp.first - 1 < n - tmp.second + tmp.first - 1) {
      nodes[k].push_back(tmp.first);
      set<int>::iterator it = s.upper_bound(tmp.first);
      while ((*it) != tmp.second) {
        nodes[k].push_back(*it);
        ++it;
      }
      nodes[k].push_back(tmp.second);
      for (int j = (1); j < (((int)nodes[k].size()) - 1); ++j)
        s.erase(nodes[k][j]);
    } else {
      set<int>::iterator it = s.begin();
      while ((*it) != tmp.first) {
        nodes[k].push_back(*it);
        ++it;
      }
      nodes[k].push_back(tmp.first);
      nodes[k].push_back(tmp.second);
      it = s.upper_bound(tmp.second);
      while (it != s.end()) {
        nodes[k].push_back(*it);
        ++it;
      }
      for (int j = (0); j < (((int)nodes[k].size())); ++j)
        if (nodes[k][j] != tmp.first && nodes[k][j] != tmp.second)
          s.erase(nodes[k][j]);
    }
    reverse(nodes[k].begin(), nodes[k].end());
  }
  ++k;
  while (((int)s.size())) {
    nodes[k].push_back(*s.begin());
    s.erase(s.begin());
  }
  reverse(nodes[k].begin(), nodes[k].end());
  sort(nodes + 1, nodes + k + 1);
  map<pair<int, int>, int> mp;
  for (int i = (1); i <= (k); ++i) {
    for (int j = (0); j < (((int)nodes[i].size()) - 1); ++j) {
      if (abs(nodes[i][j] - nodes[i][j + 1]) == 1) continue;
      if (mp.find(pair<int, int>(nodes[i][j], nodes[i][j + 1])) != mp.end()) {
        g[mp[pair<int, int>(nodes[i][j], nodes[i][j + 1])]].push_back(i);
        g[i].push_back(mp[pair<int, int>(nodes[i][j], nodes[i][j + 1])]);
        mp.erase(pair<int, int>(nodes[i][j], nodes[i][j + 1]));
      } else
        mp[pair<int, int>(nodes[i][j], nodes[i][j + 1])] = i;
    }
    if (0) {
      for (int j = (0); j < (((int)nodes[i].size())); ++j)
        cout << nodes[i][j] << " ";
      cout << endl;
    }
    if (nodes[i][0] == n && nodes[i][((int)nodes[i].size()) - 1] == 1) continue;
    if (mp.find(pair<int, int>(
            nodes[i][0], nodes[i][((int)nodes[i].size()) - 1])) != mp.end()) {
      g[mp[pair<int, int>(nodes[i][0], nodes[i][((int)nodes[i].size()) - 1])]]
          .push_back(i);
      g[i].push_back(mp[pair<int, int>(nodes[i][0],
                                       nodes[i][((int)nodes[i].size()) - 1])]);
      mp.erase(
          pair<int, int>(nodes[i][0], nodes[i][((int)nodes[i].size()) - 1]));
    } else
      mp[pair<int, int>(nodes[i][0], nodes[i][((int)nodes[i].size()) - 1])] = i;
  }
  coloring(1, 0);
  for (int i = (1); i <= (k); ++i) write_int(ans[i], ' ');
  return 0;
}
