#include <bits/stdc++.h>   using namespace std;   int n, m;   int score(pair<int, int> a) {     int d = abs(a.first - a.second);     return min(d, n - d);   }   const int N = 1e5 + 7;   int nxt[N], prv[N];   vector<int> regions[N];   vector<int> adj[N];   int level[N];   int sz[N];   void dfs1(int u, int par) {     assert(level[u] == 0);     sz[u] = 1;     for (int v : adj[u]) {       if (v == par || level[v]) continue;       dfs1(v, u);       sz[u] += sz[v];     }   }   int dfs2(int u, int par, int s) {     for (int v : adj[u]) {       if (v == par || level[v]) continue;       if (sz[v] > s / 2) return dfs2(v, u, s);     }     return u;   }   void decompose(int u, int lev) {     assert(level[u] == 0);     dfs1(u, -1);     int v = dfs2(u, -1, sz[u]);     level[v] = lev;     for (int w : adj[v])       if (!level[w]) decompose(w, lev + 1);   }   int main() {     ios::sync_with_stdio(false);     cin.tie(0);     cin >> n >> m;     vector<pair<int, int>> diags;     for (int i = 0; i < m; i++) {       int a, b;       cin >> a >> b;       diags.push_back({a, b});     }     auto cmp1 = [](pair<int, int> a, pair<int, int> b) {       return score(a) < score(b);     };     sort(diags.begin(), diags.end(), cmp1);     for (int i = 1; i <= n; i++) {       nxt[i] = 1 + i % n;     }     int id = 0, last = 0;     for (auto pr : diags) {       ++id;       int u = pr.first;       int v = pr.second;       int d = (v - u + n) % n;       if (d >= n - d) swap(u, v);       int cur = u;       while (cur != v) {         regions[id].push_back(cur);         cur = nxt[cur];       }       regions[id].push_back(v);       nxt[u] = v;       last = u;     }     ++id;     int cur = last;     while (true) {       regions[id].push_back(cur);       cur = nxt[cur];       if (cur == last) break;     }     map<pair<int, int>, vector<int>> mp;     for (int i = 1; i <= id; i++) {       for (int j = 0; j < regions[i].size(); j++) {         int u = regions[i][j];         int v = regions[i][(j + 1) % regions[i].size()];         if (u > v) swap(u, v);         mp[make_pair(u, v)].push_back(i);       }     }     for (auto pr : mp) {       assert(pr.second.size() <= 2);       if (pr.second.size() != 2) continue;       int u = pr.second[0];       int v = pr.second[1];       adj[u].push_back(v);       adj[v].push_back(u);     }     for (int i = 1; i <= id; i++) {       sort(regions[i].rbegin(), regions[i].rend());     }     vector<int> order;     for (int i = 1; i <= id; i++) {       order.push_back(i);     }     sort(order.begin(), order.end(),          [](int a, int b) { return regions[a] < regions[b]; });     decompose(1, 1);     for (int x : order) cout << level[x] <<    ;   }   