#include <bits/stdc++.h>
using namespace std;
int n, m, d[100005], a[100005], st[100005];
pair<int, int> sub[100005];
pair<int, int> temp[100005];
struct bitTree {
  int tree[100005];
  void update(int x) {
    for (; x <= n; x += (x & (-x))) tree[x]++;
  }
  int get(int x) {
    int re = 0;
    for (; x > 0; x -= (x & (-x))) re += tree[x];
    return re;
  }
} t;
int root(int x) {
  if (d[x] == 0) return x;
  return (d[x] = (root(d[x])));
}
void setup() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) cin >> sub[i].first >> sub[i].second;
  sort(sub + 1, sub + m + 1);
}
void prepare() {
  int r = 0, rig = m + 1;
  for (int i = m; i >= 1; i--) {
    while (rig - 1 != 0 && sub[rig - 1].first > sub[i].first)
      t.update(sub[--rig].second);
    if (t.get(sub[i].second) == 0) temp[++r] = sub[i];
  }
  for (int i = 1; i <= r; i++) sub[i] = temp[r - i + 1];
  m = r;
}
bool check(int x) {
  memset(d, 0, sizeof(int) * (n + 1)), memset(a, -1, sizeof(int) * (n + 1));
  int l = sub[1].first, r = 0;
  for (int i = 0; i <= x - 1; i++) st[++r] = i;
  for (int i = 1; i <= m; i++) {
    int lef = sub[i].first, pos = sub[i].second;
    while (l < lef) {
      if (a[l] != -1) st[++r] = a[l];
      l++;
    }
    while (r) {
      pos = root(pos);
      if (pos < lef) return false;
      a[pos] = st[r--];
      d[pos] = root(pos - 1);
      pos--;
    }
  }
  return true;
}
void xuly() {
  prepare();
  int l = 0, r = 100005;
  while (r - l > 1) {
    int g = ((l + r) >> 1);
    if (check(g))
      l = g;
    else
      r = g;
  }
  check(l);
  cout << l << '\n';
  for (int i = 1; i <= n; i++) cout << (a[i] == -1 ? l + 1 : a[i]) << ' ';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  setup();
  xuly();
  return 0;
}
