#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  vector<pair<int, int> > mas(m);
  int minn = 2000000000;
  for (int i = 0; i < m; i++) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    mas[i].first = l;
    mas[i].second = r;
    if (r - l + 1 < minn) {
      minn = r - l + 1;
    }
  }
  cout << minn << endl;
  for (int i = 0; i < m; i++) {
    mas[i].second = mas[i].first + minn - 1;
  }
  sort(mas.begin(), mas.end());
  vector<int> ans(n, 0);
  int cnt = 0;
  for (int i = mas[0].first; i <= mas[0].second; i++) {
    ans[i] = cnt;
    cnt++;
  }
  for (int i = 1; i < m; i++) {
    if (mas[i].first <= mas[i - 1].second) {
      int cnt = 0;
      for (int j = mas[i - 1].second + 1; j <= mas[i].second; j++) {
        ans[j] = ans[mas[i - 1].first + cnt];
        cnt++;
      }
    } else {
      int cnt = 0;
      for (int j = mas[i].first; j <= mas[i].second; j++) {
        ans[j] = cnt;
        cnt++;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << " ";
  }
  return 0;
}
