#include <bits/stdc++.h>
const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const long long MXLL = 4611686018427387903;
const int Sz = 1110111;
using namespace std;
inline void Read_rap() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
}
pair<int, int> a[Sz];
int n, m;
int ans[Sz];
int len;
bool used[Sz];
int main() {
  Read_rap();
  cin >> n >> m;
  len = n;
  for (int i = 1; i <= m; i++) {
    cin >> a[i].first >> a[i].second;
    len = min(len, a[i].second - a[i].first + 1);
  }
  sort(a + 1, a + m + 1, [](pair<int, int> &x, pair<int, int> &y) {
    if (x.second == y.second) return x.first > y.first;
    return x.second < y.second;
  });
  for (int i = 1; i <= m; i++) {
    if (a[i].first <= a[i - 1].first || a[i].second == a[i - 1].second)
      a[i].first = a[i - 1].first;
  }
  set<int> point;
  int last = 0;
  for (int i = 0; i <= n; i++) point.insert(i);
  for (int i = 1; i <= m; i++) {
    if (i != 1) {
      for (int j = a[i - 1].first; j <= min(a[i].first - 1, a[i - 1].second);
           j++)
        point.insert(ans[j]);
    }
    for (int j = max(a[i].first, last + 1);
         *point.begin() < len && j <= a[i].second; j++) {
      ans[j] = *point.begin();
      point.erase(ans[j]);
      last = j;
    }
  }
  cout << len << '\n';
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
  return 0;
}
