Alyona và mex

Cho một dãy gồm $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$ (bạn được tự chọn dãy này) và $m$ đoạn con. Đoạn con thứ $i$ được cho bởi hai số $l_i$ và $r_i$, gồm các phần tử $a_{l_i},a_{l_i+1},\dots ,a_{r_i}$.

Với mỗi đoạn con, xét giá trị $mex$ của tập các phần tử trong đoạn đó. $mex$ của một tập là số nguyên không âm nhỏ nhất không thuộc tập đó. Sau đó lấy giá trị nhỏ nhất trong $m$ giá trị $mex$ vừa tính.

Hãy chọn dãy $a$ sao cho giá trị nhỏ nhất đó là lớn nhất có thể.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_i$ và $r_i$ mô tả đoạn con thứ $i$.

Dữ liệu ra

• Dòng đầu in ra một số nguyên: giá trị nhỏ nhất lớn nhất có thể của các $mex$.
• Dòng thứ hai in ra $n$ số nguyên là dãy $a$. Mọi phần tử phải nằm trong đoạn $[0,{10}^9]$.

Bảo đảm luôn tồn tại đáp án tối ưu mà mọi phần tử của dãy nằm trong $[0,{10}^9]$. Nếu có nhiều dãy thỏa mãn, in ra dãy bất kỳ.

Ràng buộc

• $1\le n,m\le {10}^5$
• $1\le l_i\le r_i\le n$

Ví dụ