Построение

Перед началом игры традиционно проводят построение всех участников. Все участники становятся в одну шеренгу и объявляется старт. В построении должны участвовать все $n$ участников. Каждый из которых должен одеть одеяние некоторого цвета.

Для того чтобы построение было наиболее зрелищным, шеренга должна удовлетворять следующему требованию: задаются $m$ отрезков $[l_i\dots r_i]$ в шеренге, после построения на каждом таком отрезке цвета одеяний всех участников должны быть различны.

От вас требуется найти такие цвета одеяний, которые удовлетворяют этому требованию, причем минимизировав количество различных использованных цветов.

В первой строке содержатся два натуральных числа $n, m$ ($1 \le n \le 10^5$, $1 \le m \le 10^5$).

В следующих $m$ строках содержатся отрезки $[l_i\dots r_i]$ ($1 \le l_i \le r_i \le n$).

В первой строке выведите натуральное число $k$ --- минимальное количество различных использованных цветов.

В следующей строке выведите $n$ чисел $a_i$ ($1 \le a_i \le k$) --- цвет одеяния $i$-го участника. Если существует несколько ответов --- выведите любой.