#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const double eps = 1E-6;
const int LEN = 100000 + 10;
int n, m, ans[LEN];
vector<pair<int, int> > vs;
set<int> s;
bool J(int val) {
  s.clear();
  memset(ans, -1, sizeof ans);
  for (int i = 0; i <= val; i++) s.insert(i);
  int p = -1, loc = -1;
  for (int i = 0; i < m; i++) {
    int r = vs[i].first, l = vs[i].second;
    if (p == -1) p = l;
    if (loc == -1) loc = l;
    while (loc < l) {
      if (ans[loc] >= 0) s.insert(ans[loc]);
      loc++;
    }
    while (p <= r) {
      if (s.size() == 0) break;
      ans[p] = (*s.begin());
      s.erase(*s.begin());
      p++;
    }
    if (s.size() > 0) return false;
  }
  return true;
}
bool cmp(pair<int, int> a, pair<int, int> b) {
  if (a.first != b.first) return a.first < b.first;
  return a.second > b.second;
}
int main() {
  ios::sync_with_stdio(false);
  int l, r;
  while (cin >> n >> m) {
    vs.clear();
    memset(ans, 0, sizeof ans);
    int Ans = INF;
    for (int i = 0; i < m; i++) {
      cin >> l >> r;
      Ans = min(Ans, r - l + 1);
      vs.push_back(make_pair(r - 1, l - 1));
    }
    sort(vs.begin(), vs.end(), cmp);
    cout << Ans << endl;
    J(Ans - 1);
    for (int i = 0; i < n; i++) {
      if (ans[i] == -1) ans[i] = 0;
      cout << i % Ans << ' ';
    }
    cout << endl;
  }
  return 0;
}
