#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
const int MOD = 1e9 + 7;
const int MX = 1e5 + 10;
const ll INF = 1e18;
int N, M, K = 1;
pi E[MX];
vi V[MX], adj[MX];
int sub[MX], depth[MX];
bool vis[MX];
bool cmp(pi A, pi B) {
  int X = min(A.second - A.first, N - (A.second - A.first));
  int Y = min(B.second - B.first, N - (B.second - B.first));
  return X < Y;
}
void DFS1(int X, int P) {
  sub[X] = 1;
  for (auto& Y : adj[X])
    if (Y != P && !vis[Y]) {
      DFS1(Y, X);
      sub[X] += sub[Y];
    }
}
int centroid(int X, int P, int S) {
  for (auto& Y : adj[X])
    if (Y != P && !vis[Y] && sub[Y] > S / 2) return centroid(Y, X, S);
  return X;
}
void decomp(int X, int P) {
  DFS1(X, 0);
  int C = centroid(X, 0, sub[X]);
  vis[C] = true;
  depth[C] = depth[P] + 1;
  for (auto& Y : adj[C])
    if (!vis[Y]) decomp(Y, C);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M;
  for (int i = (0); i < (M); i++) {
    cin >> E[i].first >> E[i].second;
    if (E[i].first > E[i].second) swap(E[i].first, E[i].second);
  }
  sort(E, E + M, cmp);
  set<int> all;
  for (int i = (1); i < (N + 1); i++) all.insert(i);
  for (int i = (0); i < (M); i++) {
    if (E[i].second - E[i].first <= N - (E[i].second - E[i].first)) {
      V[K].push_back(E[i].first);
      auto IT = all.upper_bound(E[i].first);
      while (*IT != E[i].second) {
        V[K].push_back(*IT);
        IT++;
      }
      V[K].push_back(E[i].second);
      for (int j = (1); j < (V[K].size() - 1); j++) all.erase(V[K][j]);
    }
    if (E[i].second - E[i].first > N - (E[i].second - E[i].first)) {
      while (*all.begin() != E[i].first) {
        V[K].push_back(*all.begin());
        all.erase(all.begin());
      }
      V[K].push_back(E[i].first);
      V[K].push_back(E[i].second);
      int L = V[K].size();
      auto IT = all.upper_bound(E[i].second);
      while (IT != all.end()) {
        V[K].push_back(*IT);
        IT++;
      }
      for (; L < V[K].size(); L++) all.erase(V[K][L]);
    }
    reverse(begin(V[K]), end(V[K]));
    K++;
  }
  while (all.size() != 0) {
    V[K].push_back(*all.begin());
    all.erase(all.begin());
  }
  reverse(begin(V[K]), end(V[K]));
  K++;
  sort(V + 1, V + K);
  map<pi, int> M;
  for (int i = (1); i < (K); i++) {
    for (int j = (0); j < (V[i].size() - 1); j++) {
      if (V[i][j] - V[i][j + 1] == 1) continue;
      if (M.count({V[i][j + 1], V[i][j]})) {
        int X = M[{V[i][j + 1], V[i][j]}];
        adj[X].push_back(i), adj[i].push_back(X);
        M.erase({V[i][j + 1], V[i][j]});
      } else
        M[{V[i][j + 1], V[i][j]}] = i;
    }
    int R = V[i].size() - 1;
    if (V[i][0] == N && V[i][R] == 1) continue;
    if (M.count({V[i][R], V[i][0]})) {
      int X = M[{V[i][R], V[i][0]}];
      adj[X].push_back(i), adj[i].push_back(X);
      M.erase({V[i][R], V[i][0]});
    } else
      M[{V[i][R], V[i][0]}] = i;
  }
  decomp(1, 0);
  for (int i = (1); i < (K); i++) cout << depth[i] << " ";
}
