National Flag Plan

A country is launching a grand project – the National Flag Plan. In this plan, border soldiers are to run along the entire border holding the national flag. The border is equipped with M border posts, numbered 1 to M in a clockwise order. There are N elite border soldiers chosen as candidates for this plan. Each soldier is permanently stationed at two distinct border posts and is adept at running between these two posts. The route between these two posts is defined as the soldier's running interval. It is guaranteed that no soldier's running interval is strictly contained in another's.

The national security chief wants to know two things:

1. What is the minimum number of soldiers needed so that their running intervals cover the entire border circle?
2. For each soldier, assuming that soldier must participate in the plan, what is the minimum number of soldiers (including that soldier) needed to cover the entire border circle?

Notes on the intervals:

• The border posts lie on a circle of circumference M.
• For a soldier with endpoints a and b (input order), the running interval is defined as the clockwise arc from a to b. If a > b, then the interval spans from a to M and continues from 1 to b.

Input Format:

N M
a1 b1
a2 b2
... 
 aN bN

Output Format:

X
f1 f2 ... fN

Here, X is the minimum number of soldiers needed to cover the border. The second line contains N integers where the i^th integer denotes the minimum number of soldiers required if soldier i is forced to participate. It is guaranteed that the given intervals can cover the entire border circle.

Mathematical formulation (in LaTeX):

\text{Let } I_i = [a_i,b_i] \text{ (if } a_i \le b_i\text{) or } [a_i, b_i+M] \text{ (if } a_i > b_i\text{)}.\\
\text{Find } X = \min \{ k : \exists i_1,i_2,\dots,i_k \text{ such that } \bigcup_{j=1}^{k} I_{i_j} \supset [x, x+M] \text{ for some } x \in [1,M] \}.\\
\text{For each } i, \; f_i = \min \{ k : \exists S \subseteq \{1,2,\dots,N\}, i \in S \text{ and } \bigcup_{j \in S}I_j \supset [a_i, a_i+M] \}.

inputFormat

The first line contains two integers N and M, the number of soldiers and the number of border posts respectively. N lines follow, each containing two integers a and b representing the two border posts that a soldier is stationed at. Note that the running interval for a soldier is defined as the clockwise path from a to b. If a > b, the interval wraps around, covering [a, M] and [1, b].

outputFormat

The output consists of two lines. The first line contains a single integer, the minimum number of soldiers needed to cover the entire border circle. The second line contains N integers, where the i^th number is the minimum number of soldiers required to cover the border if soldier i is forced to participate. If no solution exists, output -1 (though it is guaranteed that a solution exists).

sample

3 10
8 3
2 6
5 9

3
3 3 3

</p>