#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
struct cd {
  int n;
  vector<vector<int>> adj;
  vector<int> subtree_size;
  vector<vector<int>> children;
  vector<int> mark;
  void dfs0(int i, int depth) {
    mark[i] = subtree_size[i] = 0;
    for (int j : adj[i])
      if (mark[j] == 1) dfs0(j, depth);
  }
  int dfs1(int i) {
    mark[i] = subtree_size[i] = 1;
    for (int j : adj[i])
      if (mark[j] == 0) {
        subtree_size[i] += dfs1(j);
      }
    return subtree_size[i];
  }
  int find_centroid(int i, int cnt, int p = -1) {
    bool is_centroid = cnt - subtree_size[i] <= cnt / 2;
    int j_heavy = -1;
    for (int j : adj[i])
      if (j != p && mark[j] == 1) {
        if (subtree_size[j] > cnt / 2) is_centroid = false;
        if (j_heavy == -1 || subtree_size[j] > subtree_size[j_heavy])
          j_heavy = j;
      }
    if (is_centroid) return i;
    return find_centroid(j_heavy, cnt, i);
  }
  int decompose_tree(int i, int depth = 0) {
    if (depth) dfs0(i, depth - 1);
    int cnt = dfs1(i);
    i = find_centroid(i, cnt);
    mark[i] = 2;
    for (int j : adj[i])
      if (mark[j] != 2) {
        children[i].push_back(decompose_tree(j, depth + 1));
      }
    return i;
  }
  vector<int> centroid_decomp(vector<vector<int>> aadj) {
    adj = aadj;
    n = int((adj).size());
    subtree_size.resize(n);
    mark.resize(n);
    children.resize(n);
    int rt = decompose_tree(0);
    vector<int> col(n);
    queue<int> q;
    col[rt] = 1;
    q.push(rt);
    while (int((q).size())) {
      int i = q.front();
      q.pop();
      for (int j : children[i]) {
        col[j] = col[i] + 1;
        q.push(j);
      }
    }
    return col;
  }
} foo;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> adj(n);
  for (int i = (0); i < (n); i++) adj[i].push_back((i + 1) % n);
  for (int i = (0); i < (n); i++) adj[i].push_back((i + n - 1) % n);
  map<pair<int, int>, int> edge_id;
  for (int i = (0); i < (m); i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    edge_id[make_pair(a, b)] = i;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for (int i = (0); i < (n); i++) sort(begin(adj[i]), end(adj[i]));
  set<pair<int, int>> done;
  vector<pair<vector<int>, vector<int>>> faces;
  for (int i = (0); i < (n); i++)
    for (const int &j : adj[i]) {
      if (((done).find(make_pair(i, j)) != end(done))) continue;
      if (j == (i + 1) % n) continue;
      vector<int> cur = {i, j};
      vector<int> ids;
      int a = i, b = j;
      done.emplace(i, j);
      if (((edge_id).find(make_pair(i, j)) != end(edge_id)))
        ids.push_back(edge_id[make_pair(i, j)]);
      if (((edge_id).find(make_pair(j, i)) != end(edge_id)))
        ids.push_back(edge_id[make_pair(j, i)]);
      while (true) {
        auto it = lower_bound(begin(adj[b]), end(adj[b]), a);
        it++;
        if (it == end(adj[b])) it = begin(adj[b]);
        int c = *it;
        done.emplace(b, c);
        if (((edge_id).find(make_pair(b, c)) != end(edge_id)))
          ids.push_back(edge_id[make_pair(b, c)]);
        if (((edge_id).find(make_pair(c, b)) != end(edge_id)))
          ids.push_back(edge_id[make_pair(c, b)]);
        if (c == i) break;
        cur.push_back(c);
        a = b, b = c;
      }
      sort(begin(cur), end(cur), greater<int>());
      faces.emplace_back(cur, ids);
    }
  sort(begin(faces), end(faces), greater<pair<vector<int>, vector<int>>>());
  reverse(begin(faces), end(faces));
  vector<vector<int>> edge_ends(m);
  int ii = 0;
  for (const auto &p : faces) {
    for (const auto &j : p.second) edge_ends[j].push_back(ii);
    ii++;
  }
  vector<vector<int>> adj_tree(int((faces).size()));
  for (int i = (0); i < (m); i++) {
    int a = edge_ends[i][0], b = edge_ends[i][1];
    adj_tree[a].push_back(b);
    adj_tree[b].push_back(a);
  }
  vector<int> col = foo.centroid_decomp(adj_tree);
  for (int i = (0); i < (m + 1); i++) cout << col[i] << " \n"[i == m];
}
