#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
class diagonal {
 public:
  int x, y, dis, direct;
  diagonal(int iX = 0, int iY = 0, int iDis = 0, int iDirect = 0) {
    x = iX;
    y = iY;
    dis = iDis;
    direct = iDirect;
  }
};
bool cmpVertices(int a, int b) { return a > b; }
class region {
 public:
  vector<int> vertices;
  int fa;
  int color;
  region(vector<int> iVertices = vector<int>(0), int iColor = -1,
         int iFa = -1) {
    vertices = iVertices;
    color = iColor;
    sort(vertices.begin(), vertices.end(), cmpVertices);
    fa = iFa;
  }
};
diagonal diagonals[MAXN];
region regions[MAXN];
vector<int> son[MAXN];
int nextX[MAXN], nextY[MAXN];
int nextXID[MAXN], nextYID[MAXN];
int rootNow[MAXN];
int n, m, regionN;
int nodeID;
bool diagonalCmp(diagonal a, diagonal b) { return a.dis < b.dis; }
bool regionCmp(region a, region b) {
  for (int i = 0; i < a.vertices.size() && i < b.vertices.size(); i++)
    if (a.vertices[i] < b.vertices[i])
      return true;
    else if (a.vertices[i] > b.vertices[i])
      return false;
  return true;
}
int DFS(int x) {
  int treeN = 1;
  for (int i = 0; i < son[x].size(); i++) {
    int y = son[x][i];
    if (regions[y].fa != -1) {
      treeN += DFS(y);
    }
  }
  return treeN;
}
int findCenter(int x, int centerN) {
  if (nodeID != -1) return 0;
  int treeN = 1;
  if (treeN >= centerN) {
    nodeID = x;
    return 0;
  }
  for (int i = 0; i < son[x].size(); i++) {
    int y = son[x][i];
    if (regions[y].fa != -1) {
      treeN += findCenter(y, centerN);
      if (treeN >= centerN) {
        nodeID = x;
        return 0;
      }
      if (nodeID != -1) return 0;
    }
  }
  return treeN;
}
void colorRegion(int rootID, int color) {
  int y;
  int treeN = DFS(rootID);
  if (treeN == 1) {
    if (regions[rootID].color == -1) regions[rootID].color = color;
    return;
  }
  nodeID = -1;
  findCenter(rootID, treeN / 2);
  regions[nodeID].color = color;
  regions[nodeID].fa = -1;
  for (int i = 0; i < son[nodeID].size(); i++) {
    y = son[nodeID][i];
    regions[y].fa = -1;
  }
  return;
}
int main() {
  int x, y, dis, direct, i, j;
  vector<int> v;
  scanf("%d%d", &n, &m);
  for (int i = 1; i < m + 1; i++) {
    scanf("%d%d", &x, &y);
    if (x > y) swap(x, y);
    if (y - x - 1 <= n - 2 - (y - x - 1)) {
      diagonals[i] = diagonal(x, y, (y - x - 1), 1);
    } else {
      diagonals[i] = diagonal(x, y, (n - 2 - (y - x - 1)), -1);
    }
  }
  for (int i = 1; i < n + 1; i++) {
    x = i - 1;
    if (x == 0) x = n;
    y = (i + 1) % n;
    if (y == 0) y = n;
    nextX[i] = x;
    nextY[i] = y;
    nextXID[i] = -1;
    nextYID[i] = -1;
  }
  sort(diagonals + 1, diagonals + m + 1, diagonalCmp);
  regionN = 0;
  for (int k = 1; k < m + 1; k++) {
    x = diagonals[k].x;
    y = diagonals[k].y;
    direct = diagonals[k].direct;
    v.clear();
    regionN++;
    if (direct == 1) {
      i = x;
      int index = 0;
      while (i != y) {
        index++;
        j = nextY[i];
        v.push_back(i);
        if (nextYID[i] != -1) {
          regions[nextYID[i]].fa = regionN;
          nextYID[i] = -1;
        }
        nextY[i] = -1;
        nextX[j] = -1;
        i = j;
      }
      v.push_back(y);
      nextY[x] = y;
      nextX[y] = x;
      nextYID[x] = regionN;
      nextXID[y] = regionN;
    } else if (direct == -1) {
      i = x;
      int index = 0;
      while (i != y) {
        index++;
        j = nextX[i];
        v.push_back(i);
        if (nextXID[i] != -1) {
          regions[nextXID[i]].fa = regionN;
          nextXID[i] = -1;
        }
        nextX[i] = -1;
        nextY[j] = -1;
        i = j;
      }
      v.push_back(y);
      nextX[x] = y;
      nextY[y] = x;
      nextXID[x] = regionN;
      nextYID[y] = regionN;
    }
    regions[regionN] = region(v);
  }
  regionN++;
  v.clear();
  for (int i = 1; i < n + 1; i++) {
    if (nextX[i] != -1) {
      regions[nextXID[i]].fa = regionN;
      v.push_back(i);
    }
  }
  regions[regionN] = region(v);
  memset(rootNow, 0, sizeof(rootNow));
  for (int i = 1; i < regionN; i++) {
    son[regions[i].fa].push_back(i);
  }
  int sum = 0;
  for (int i = 1; i < regionN + 1; i++)
    if (regions[i].fa == -1) {
      sum++;
    }
  if (sum > 1) {
    cout << "build tree error" << endl;
    return 0;
  }
  for (int k = 1; k < 21; k++) {
    for (int i = 1; i < regionN + 1; i++)
      if (regions[i].fa == -1) rootNow[i] = k;
    for (int i = 1; i < regionN + 1; i++)
      if (rootNow[i] == k) {
        colorRegion(i, k);
      }
  }
  sort(regions + 1, regions + regionN + 1, regionCmp);
  for (int i = 1; i < regionN; i++) printf("%d ", regions[i].color);
  printf("%d\n", regions[regionN].color);
  return 0;
}
