시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB997100.000%

문제

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

예제 입력 1

3 1
2 3

예제 출력 1

2
2 2 1

예제 입력 2

6 3
2 3
4 6
3 6

예제 출력 2

4
3 3 2 3 1 4

예제 입력 3

5 3
4 5
2 2
3 3

예제 출력 3

2
1 1 1 1 2