#include <bits/stdc++.h>
using namespace std;
const long long LINF = 334ll << 53;
const int INF = 15 << 26;
const long long MOD = 1E9 + 7;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m, l[100010] = {}, r[100010] = {}, mmex = INF, ans[100010] = {},
            cnt[100010] = {};
  fill(ans, ans + 100010, -1);
  vector<int> a;
  cin >> n >> m;
  vector<pair<int, int>> b(m);
  for (int(i) = 0; (i) < (m); ++(i)) {
    cin >> b[i].first >> b[i].second;
    b[i].first--;
    b[i].second--;
    mmex = min(mmex, b[i].second - b[i].first + 1);
  }
  sort(b.begin(), b.end());
  int t = 0, p = 0;
  for (int(i) = 0; (i) < (m); ++(i)) {
    if ((b[i].second - b[i].first + 1) == mmex) {
      p = max(p, b[i].first);
      for (int(j) = (p); (j) < (b[i].second + 1); ++(j)) {
        ans[j] = t;
        cnt[j + 1] = 1;
        t = (t + 1) % mmex;
        p++;
      }
    }
  }
  for (int(i) = 0; (i) < (n); ++(i)) cnt[i + 1] += cnt[i];
  p = 0;
  int q = 0;
  for (int(i) = 0; (i) < (m); ++(i)) {
    if ((b[i].second - b[i].first + 1) != mmex) {
      int y = cnt[b[i].first];
      int z = cnt[b[i].second + 1];
      q = max(b[i].first, p);
      for (int(j) = (q); (j) < (b[i].second + 1); ++(j)) {
        if (ans[j] == -1) {
          if (z - y >= mmex) break;
          ans[j] = z % mmex;
          p = j;
          z = (z + 1);
        }
      }
      p++;
    }
  }
  for (int(i) = 0; (i) < (n); ++(i))
    if (ans[i] == -1) ans[i] = 0;
  cout << mmex << endl;
  for (int(i) = 0; (i) < (n - 1); ++(i)) cout << i % mmex << ' ';
  cout << (n - 1) % mmex << endl;
  return 0;
}
