Channels without interference

backtracking coloring graph heuristic geodata

Transmitters are being installed in the towns around Almaty, one in each. Two transmitters closer than D kilometres to each other interfere on the same channel; on different channels or farther apart they do not. Every channel costs money, so as few channels as possible are needed. How many will be enough, and how should they be assigned?

Tests 3–5 are real towns of 10 thousand inhabitants and more within 300 km of Almaty from the GeoNames gazetteer, put on a flat map to the nearest kilometre, with different D. The other layouts are made up.

Input

The first line holds the number of transmitters n and the distance D (1 ≤ n ≤ 40, 1 ≤ D ≤ 10⁴). Then n lines with the coordinates of the transmitters x y in kilometres, integers, |x|, |y| ≤ 10⁴. Transmitters interfere on the same channel if the distance between them is strictly less than D. Different transmitters may have the same coordinates.

Output

The first line is the smallest number of channels k. The second holds n numbers from 1 to k: the channel of each transmitter in input order. If there are several ways, print any.

Examples

Example 1

Input

Output

2
2 1 2 1

Example 2

Input

Output

3
1 2 1 2 3

Limits

Time · Python: 6000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 13 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

The transmitters are the vertices of a graph, and the pairs that interfere are its edges. Assigning channels means colouring the vertices so that the ends of every edge have different colours. The first thing that comes to mind is to go through the transmitters and give each the smallest channel not taken by its neighbours. This always gives a valid assignment, but is it the smallest? Check on the eighth test.

2Hint 2

There is a lower bound: if m transmitters interfere pairwise, they need m different channels. But is this number always enough? Look at the second sample: five transmitters in a ring, neighbours interfere, but every other one does not. At most two interfere pairwise, yet three channels are needed.

3Hint 3

Since there is no formula, we have to search. Use backtracking to check whether k channels are enough, for k from the lower bound upwards. For the search to be fast enough you need three things: which transmitter to colour next, how not to try assignments that differ only in channel numbers, and where to start k.

4The idea

For k = the lower bound, the lower bound + 1, … look for a colouring in k colours by backtracking. Colour next the transmitter with the fewest free channels (on a tie, the one with more neighbours). A new, not yet used channel is given only as the smallest of the unused numbers: channels are interchangeable, and there is no point trying assignments that differ only by a permutation of numbers. The first k for which a colouring is found is the answer: for smaller ones the search has proved there is none.

5Walkthrough

The graph. An edge between i and j if (x_i − x_j)² + (y_i − y_j)² < D², in integers, without square roots.

The lower bound. A clique is a group of pairwise adjacent vertices. Finding the largest clique is a hard problem too, but a greedy one is enough for a bound: from every vertex grow a clique, adding the neighbour with the most common neighbours with those already taken. The better the bound, the fewer useless k have to be refuted. In the tests with real towns the greedy clique gives the answer at once: there the towns cluster tightly around the big cities, and the answer is set by the densest cluster.

The search. For each vertex keep how many of its neighbours are already coloured in each colour; the free colours are those with a zero count. At each step pick the uncoloured vertex with the fewest free colours: if some vertex has none, the branch is dead, and we go back at once. Try colours in increasing order, but not above “the largest used + 1”. On backtracking decrease the neighbours' counts.

Why this is correct. The pruning loses only assignments obtained from already considered ones by permuting channel numbers, and a permutation does not change the answer. A branch where a vertex has no free colour is pointless to continue: that colour will not appear however the others are coloured.

5+Solution

6Complexity

Graph colouring is NP-hard, and in the worst case the search is exponential. Here n ≤ 40, and the graphs are geometric: a transmitter's neighbours are close to each other and are neighbours too. On such graphs choosing the most constrained vertex forces channels almost at once, and the reference in Python solves each test in fractions of a second. But a search in input order, without the most constrained vertex and without forbidding extra numbers, does not find an assignment with 21 channels on the thirteenth test even in a minute, although the lower bound there is exactly 21.

7Common mistakes

The greedy assignment. Valid, but not the smallest: on the eighth test it gives 13 channels instead of 11, on the thirteenth 25 instead of 21.
The answer is the size of the largest clique. Rings of five and seven transmitters (the second, sixth and seventh tests) need one channel more.
All channel numbers for a new vertex. If a vertex may take any of the k unused numbers, each assignment repeats up to k! times, and proving that k channels are too few will not work in reasonable time.
Distance in floating point. The boundary “strictly less than D” on integer coordinates is checked exactly in squares; a square root can turn an equality into an inequality.

Algorithms behind it

PAR Technique Backtracking Build a solution step by step, check at once and retreat from dead ends: sudoku, queens, colourings. O(bᵈ) in the worst case 2 problems GRA Algorithm Graph colouring Different colours for neighbours: the greedy way, the smallest-last order, DSatur and exact search on maps and timetables. O(V + E) for greedy in a given order and smallest last; O((V + E) log V) for DSatur with a heap 2 problems