## An Animal Contest 6 P2 - G-Pop

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem types

Kyriakos Grizzly is organizing a G-Pop (Grizzly-Pop) concert for his friends! The concert consists of 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 shows. Since Kyriakos' friends are very busy, the of his friends can only attend the concerts from to performance (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!

#### Input Specification

The first line of input will contain spaced out integers and . The next lines will each contain integers with the of these lines containing and .

#### Output Specification

The first line of output will contain a single integer , the minimum number of different bands Kyriakos has to hire to be in his concert.

The final line of output will contain spaced out integers each in the range , with the integer denoting the id of the band performing at the performance.

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

#### Scoring

For each test case:

• If you correctly determine the optimal but you output an invalid plan, you will receive 20% of the available marks.
• If you correctly determine the optimal 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 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