#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
const int oo = 1e9 + 7;
int n, m, res, f[N], id[N], a[N];
void home() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
void enter() {
  cin >> n >> m;
  int l, r;
  res = oo;
  for (int(i) = (1); i <= (m); ++i) {
    cin >> l >> r;
    ++f[l];
    --f[r + 1];
    res = ((res) < (r - l + 1) ? (res) : (r - l + 1));
  }
}
bool by(int i, int j) { return f[i] > f[j]; }
void solve() {
  for (int(i) = (1); i <= (n); ++i) f[i] += f[i - 1], id[i] = i;
  sort(id + 1, id + n + 1, by);
  cout << res << "\n";
  int cnt = 0;
  for (int(i) = (1); i <= (n); ++i)
    if (f[i] == 0)
      cout << 0 << " ";
    else {
      cout << cnt << " ";
      if (++cnt >= res) cnt = 0;
    }
}
int main() {
  home();
  enter();
  solve();
}
