19040번 - Labeled Points 다국어

Consider $N$ points on the Cartesian plane. The points are labeled with positive integers from $1$ to $N$. The points are special: for each point $(x_i, y_i)$, the coordinates are positive integers, and the equality $x_i \bmod 2 = \lfloor y_i / 2 \rfloor \bmod 2$ holds.

Your task is to select a sequence of $K$ of those points with the following property: the distance between every pair of points from this sequence is not less than $2$. Among all such sequences, find the one for which the sequence of the points' labels is lexicographically minimal.

The first line of input contains two integers $N$ and $K$ ($2 \le K \le N \le 6000$). Each of the next $N$ lines contains coordinates of a point: two integers $x_i$ and $y_i$  ($1 \le x_i, y_i \le 10^9$, $x_i \bmod 2 = \lfloor y_i / 2 \rfloor \bmod 2$).

It is guaranteed that all given points are pairwise distinct.

If it is impossible to select $K$ points so that the distance between every pair of them is not less than $2$, print $-1$. Otherwise, print $K$ integers, one integer per line: the sequence with the desired property which is lexicographically minimal.