Mảng và mex

Cho hai số nguyên dương $n$ và $m$. Bạn cần xây dựng một mảng $a$ gồm $n$ số nguyên không âm sao cho giá trị nhỏ nhất trong số $m$ giá trị mex của các đoạn con cho trước là lớn nhất có thể.

Mỗi đoạn con được mô tả bởi hai chỉ số $l_i$ và $r_i$ và bao gồm các phần tử $a_{l_i},a_{l_i+1},\dots ,a_{r_i}$.

Hàm mex của một tập $S$ là số nguyên không âm nhỏ nhất không xuất hiện trong $S$.

Hãy in ra giá trị tối đa của giá trị mex nhỏ nhất và mảng $a$ đạt được giá trị đó.

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 giá trị tối đa của giá trị mex nhỏ nhất trong $m$ đoạn con.
• Dòng thứ hai in ra $n$ số nguyên là các phần tử của mảng $a$. Các phần tử phải nằm trong đoạn $[0,{10}^9]$.

Nếu có nhiều mảng thoả mãn, in ra bất kỳ mảng nào.

Ràng buộc

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

Ví dụ