405618: GYM102012 H Rikka with A Long Colour Palette

Blue, the colour of the sky, the sea and your eyes.

Green, the colour of nature, fertility and life.

Purple, the colour of good judgment, and of people seeking spiritual fulfilment.

Orange, the only colour that is also a fruit.

Yellow, the colour in smiley faces.

Red, the warmest of all.

Rikka loves them all, but what is her favourite colour? She has found $$$k$$$ different colours, numbered from $$$1$$$ to $$$k$$$, and she knows that the best colour should be the one after mixing them all together. The best colour is called the DREAM.

Rikka has also prepared a long and narrow colour palette of length $$$10^9$$$. She designates $$$n$$$ segments in the palette. A segment described by two integers $$$l$$$ and $$$r$$$ ($$$0 \le l < r \le 10^9$$$) represents an area of the palette where the distance between the leftmost end of the palette and the left endpoint (resp. the right endpoint) of the area is $$$l$$$ (resp. $$$r$$$).

She will for each segment designated smear the pigment of any of these colours (from $$$1$$$ to $$$k$$$) which she has found evenly on it. Some areas may contain pigments of several different colours, since these segments may intersect. If some areas contain all these $$$k$$$ different colours which she has found, it would blend into the DREAM.

Now, Rikka wants you to maximize the total length of all areas in the palette such that each part of them can blend into the DREAM. You also need to provide a feasible plan.

The input contains several test cases, and the first line contains a single integer $$$T$$$ ($$$1 \le T \le 1000$$$), the number of test cases.

For each test case, the first line contains two integers $$$n$$$ ($$$1 \le n \le 2 \times 10^5$$$), the number of segments designated by Rikka, and $$$k$$$ ($$$1 \le k \le 2 \times 10^5$$$), the number of colours which Rikka has found.

Each of the following $$$n$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$0 \le l < r \le 10^9$$$), representing the $$$i$$$-th segment in the palette.

The input guarantees that the sum of $$$n$$$ in all test cases is at most $$$2 \times 10^6$$$.

For each test case, output two lines. Firstly, output a line with a single integer, the largest total length of areas required. Then, output a line with $$$n$$$ space-separated integers describing a feasible plan, where the $$$i$$$-th number is the colour for the $$$i$$$-th segment.

All feasible plans are allowed, so you can output any of them.

1
3 2
1 5
2 4
3 6

3
1 2 2