A. Алёна и mex
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мама хочет подарить маленькой девочке Алёне массив из n целых неотрицательных чисел. Но массив должен быть особенным.

Алёна девочка капризная, поэтому когда мама подарит ей массив, Алёна рассмотрит m подмассивов подаренного ей массива. Назовем подмассивом некоторую последовательность из подряд идущих чисел в массиве. i-й подмассив задается двумя числами li и ri, и он состоит из чисел a[li], a[li + 1], ..., a[ri].

Капризная Алёна посмотрит на mex каждого подмассива. Среди всех m mex-ов девочка выберет минимальный, и она хотела бы, чтобы минимальный mex был как можно больше.

Ваша задача найти массив a из n неотрицательных чисел такой, чтобы минимальный mex подмассивов, заданных Алёной, был максимален.

mex множества чисел S — это минимальное неотрицательное целое число, которое не встречается в множестве S.

Входные данные

В первой строке находятся два числа n и m (1 ≤ n, m ≤ 105).

В следующих m строках задано описание подмассивов, интересующих Алёну. В i-й из этих строк заданы два числа li и ri (1 ≤ li ≤ ri ≤ n), которым соответствует подмассив a[li], a[li + 1], ..., a[ri].

Выходные данные

В первой строке выведете одно число — максимально возможный минимальный mex.

Во второй строке выведете n чисел — массив a. Числа в массиве a должны быть от 0 до 109.

Гарантируется, что существует оптимальный ответ, в котором все числа в массиве a находятся в пределах от 0 до 109.

Если существует несколько решений, выведите любое.

Примеры
Входные данные
5 3
1 3
2 5
4 5
Выходные данные
2
1 0 2 1 0
Входные данные
4 2
1 4
2 4
Выходные данные
3
5 2 0 1
Примечание

Пояснение к тесту из условия: на подмассиве (1, 3) mex равен 3, на подмассиве (2, 5) mex равен 3 и на подмассиве (4, 5) mex тоже равен 2, следовательно минимальный mex среди подмассивов, интересующих Алёну, равен 2.