Построение

Перед началом игры традиционно проводят построение всех участников. Все участники становятся в одну шеренгу и объявляется старт. В построении должны участвовать все $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$-го участника. Если существует несколько ответов --- выведите любой.