#include <bits/stdc++.h>
using namespace std;
int a[100001], n, m;
vector<pair<int, int>> v;
stack<pair<int, int>> st;
vector<pair<int, int>> imp;
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1, a, b; i <= m; i++) {
    scanf("%d %d", &a, &b);
    v.push_back(make_pair(a, b));
  }
  sort(v.begin(), v.end());
  for (unsigned int i = 0; i < m; i++) {
    if (st.empty()) {
      st.push(v[i]);
      continue;
    }
    if (st.top().first == v[i].first) continue;
    while (!st.empty() && st.top().second >= v[i].second) st.pop();
    st.push(v[i]);
  }
  while (!st.empty()) imp.push_back(st.top()), st.pop();
  sort(imp.begin(), imp.end());
  int ans = 1e9;
  for (unsigned int i = 0; i < imp.size(); i++)
    ans = min(ans, imp[i].second - imp[i].first + 1);
  printf("%d\n", ans);
  for (int i = 1; i <= n; i++) a[i] = -1;
  int bef = 0;
  for (unsigned int i = 0; i < imp.size(); i++) {
    int s = imp[i].first, e = imp[i].second;
    if (a[s] == -1) {
      for (int j = s, k = 0; j <= e; j++, k = (k + 1) % ans) a[j] = k;
      bef = e;
    } else {
      for (int j = bef + 1, k = (a[bef] + 1) % ans; j <= e;
           j++, k = (k + 1) % ans)
        a[j] = k;
      bef = e;
    }
  }
  for (int i = 1; i <= n; i++)
    if (a[i] == -1) a[i] = 0;
  for (int i = 1; i <= n; i++) printf("%d ", a[i]);
  return 0;
}
