#include <bits/stdc++.h>
using namespace std;
int n, m, l, r, mid, bj[1001000];
queue<int> dl;
struct node {
  int l, r;
} ask[1001000];
int ans, a[1001000];
bool cmp(const node& a, const node& b) {
  if (a.l == b.l)
    return a.r < b.r;
  else
    return a.l < b.l;
}
int main() {
  cin >> n >> m;
  ans = 0x7fffffff;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &ask[i].l, &ask[i].r);
    ans = min(ask[i].r - ask[i].l + 1, ans);
  }
  sort(ask + 1, ask + m + 1, cmp);
  int lax = 0, cnt = 0;
  int be = 0;
  for (int i = 0; i < ans; i++) dl.push(i);
  for (int i = 1; i <= m; i++) {
    l = ask[i].l, r = ask[i].r;
    be = max(l - 1, be);
    if (l == ask[i - 1].l) continue;
    for (int j = lax; j < l; j++)
      if (bj[a[j]]) {
        cnt++;
        bj[a[j]] = 0;
        dl.push(a[j]);
      }
    for (int j = be + 1; j <= r; j++) {
      if (dl.empty()) break;
      be = max(j, be);
      int x = dl.front();
      dl.pop();
      a[j] = x;
      bj[x] = 1;
    }
    lax = l;
  }
  cout << ans << endl;
  for (int i = 1; i <= n; i++) printf("%d ", a[i]);
  return 0;
}
