#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 1e5 + 20;
pair<vector<vector<int>>, vector<pair<int, int>>> buildDual(
    int n, vector<pair<int, int>>& edges) {
  vector<vector<int>> faces;
  vector<pair<int, int>> faceEdges;
  vector<pair<int, int>> edgePos(edges.size());
  vector<vector<pair<int, int>>> graph(n);
  vector<vector<bool>> visited(n);
  vector<vector<int>> whichFace(n);
  for (int i = 0; i < edges.size(); ++i) {
    graph[edges[i].first].push_back({edges[i].second, i});
    graph[edges[i].second].push_back({edges[i].first, i});
  }
  for (int node = 0; node < n; ++node) {
    auto cmp = [&](pair<int, int> a, pair<int, int> b) {
      if (a.first < node) a.first += n;
      if (b.first < node) b.first += n;
      return a.first < b.first;
    };
    sort(graph[node].begin(), graph[node].end(), cmp);
    for (int i = 0; i < graph[node].size(); ++i) {
      int edgeIndex = graph[node][i].second;
      if (edges[edgeIndex].first == node)
        edgePos[edgeIndex].first = i;
      else
        edgePos[edgeIndex].second = i;
    }
    visited[node].resize(graph[node].size());
    whichFace[node].resize(graph[node].size());
  }
  auto getCorrespondent = [&](int x, int ind) {
    int edgeIndex = graph[x][ind].second;
    if (x == edges[edgeIndex].first) {
      return make_pair(edges[edgeIndex].second, edgePos[edgeIndex].second);
    } else {
      return make_pair(edges[edgeIndex].first, edgePos[edgeIndex].first);
    }
  };
  for (int node = 0; node < n; ++node) {
    for (int i = 0; i < graph[node].size(); ++i) {
      if (i != graph[node].size() - 1) {
        if (!visited[node][i]) {
          vector<int> faceVertices;
          int x = node;
          int ind = i;
          while (!visited[x][ind]) {
            faceVertices.push_back(x);
            visited[x][ind] = true;
            whichFace[x][ind] = faces.size();
            tie(x, ind) = getCorrespondent(x, ind);
            ind = ind - 1;
          }
          faces.push_back(faceVertices);
        }
        if (i != 0) {
          faceEdges.push_back({whichFace[node][i], whichFace[node][i - 1]});
        }
      }
    }
  }
  return {faces, faceEdges};
}
tuple<int, int, int> getFarthestDfs(vector<vector<int>>& tree, int x, int f,
                                    int d, vector<int>& st) {
  st.push_back(x);
  auto bestFound = make_tuple(d, x, st[st.size() >> 1]);
  for (auto y : tree[x]) {
    if (y == f || y == -1) continue;
    auto newFound = getFarthestDfs(tree, y, x, d + 1, st);
    if (get<0>(newFound) > get<0>(bestFound)) bestFound = newFound;
  }
  st.pop_back();
  return bestFound;
}
void centroidDecomposition(vector<vector<int>>& tree, vector<int>& info,
                           int root, int father, int curCol) {
  int rememberPos = -1;
  for (int i = 0; i < tree[root].size(); ++i) {
    if (tree[root][i] == father) {
      tree[root][i] = -1;
      rememberPos = i;
    }
  }
  vector<int> st;
  int farthest = get<1>(getFarthestDfs(tree, root, -1, 0, st));
  int centroid = get<2>(getFarthestDfs(tree, farthest, -1, 0, st));
  info[centroid] = curCol;
  for (auto son : tree[centroid]) {
    if (son != -1) centroidDecomposition(tree, info, son, centroid, curCol + 1);
  }
  if (rememberPos != -1) tree[root][rememberPos] = father;
}
void solve() {
  int n, m;
  scanf("%d %d", &n, &m);
  vector<pair<int, int>> edges;
  for (int i = 0; i < n; ++i) {
    edges.push_back({i, (i + 1) % n});
  }
  for (int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x;
    --y;
    edges.push_back({x, y});
  }
  vector<vector<int>> faces;
  vector<pair<int, int>> faceEdges;
  tie(faces, faceEdges) = buildDual(n, edges);
  vector<vector<int>> tree(faces.size());
  vector<int> color(faces.size());
  for (auto edge : faceEdges) {
    tree[edge.first].push_back(edge.second);
  }
  centroidDecomposition(tree, color, 0, -1, 1);
  vector<pair<vector<int>, int>> indexedFaces(faces.size());
  for (int i = 0; i < indexedFaces.size(); ++i) {
    indexedFaces[i] = {faces[i], i};
    sort(indexedFaces[i].first.rbegin(), indexedFaces[i].first.rend());
  }
  sort(indexedFaces.begin(), indexedFaces.end());
  for (int i = 0; i < indexedFaces.size(); ++i) {
    cout << color[indexedFaces[i].second] << " ";
  }
}
void reset() {}
int main() {
  int tests = 1;
  for (; tests; --tests) {
    solve();
    reset();
  }
}
