시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

3 2
2 1
1 2
1 3

예제 출력 1

1
3

예제 입력 2

4 3
2 1
1 2
1 3
2 4

예제 출력 2

-1

예제 입력 3

5 3
5 7
5 6
6 8
20 20
4 8

예제 출력 3

2
3
4