Kyriakos Grizzly is organizing a G-Pop (Grizzly-Pop) concert for his ~Q~ friends! The concert consists of ~N~ shows where each show has a G-pop band performing in it. Note that a certain band may perform multiple times over the period of the ~N~ shows. Since Kyriakos' friends are very busy, the ~i^\text{th}~ of his friends can only attend the concerts from ~l_i~ to performance ~r_i~ (inclusive). Also, his friends will get bored if they listen to the same band more than once. Kyriakos wants to design a concert plan in which none of his friends gets bored. Also, since his friends are extremely impatient, Kyriakos wants to design a plan with the minimum number of band changes. A band change occurs when two different bands perform in consecutive concerts. In addition, he is trying to save money so this plan should minimize the number of distinct bands playing. Help Kyriakos determine a concert plan!

Constraints

~1 \le N \le 5 \times 10^5~

~0 \le Q \le \min(5 \times 10^5, \frac{N(N+1)}{2})~

Input Specification

The first line of input will contain ~2~ spaced out integers ~N~ and ~Q~. The next ~Q~ lines will each contain ~2~ integers with the ~i^\text{th}~ of these lines containing ~l_i~ and ~r_i~.

Output Specification

The first line of output will contain a single integer ~K~ ~(1 \le K \le 10^9)~, the minimum number of different bands Kyriakos has to hire to be in his concert.

The final line of output will contain ~N~ spaced out integers each in the range ~[1, K]~, with the ~i^\text{th}~ integer denoting the id of the band performing at the ~i^\text{th}~ performance.

If there are multiple valid plans, you may output any of them.

Scoring

For each test case:

• If you correctly determine the optimal ~K~ but you output an invalid plan, you will receive 20% of the available marks.
• If you correctly determine the optimal ~K~ and you output a valid plan but you do not minimize the number of band changes you will receive another 30% of the marks.
• If you correctly determine the optimal ~K~ and output a valid plan with the minimum number of band changes, you will receive the other 50% of the marks.
• If your output is malformed in any way, you will automatically receive 0% of the available marks.

Your final score is the minimum score over all test cases.

Note: A valid plan is one that uses an optimal number of different bands, and makes sure that none of Kyriakos' friends get bored. A valid plan may not have the optimal number of band changes.

Sample Input

5 3
1 4
2 4
3 5

Sample Output

4
1 2 3 4 2