Description

On a 2D plane, there are $n$ grid cells where skyscrapers are planned to be built. The planned cell of the $i$-th skyscraper is located at $(r_i, c_i)$.

You may choose any construction order of the skyscrapers, but it must satisfy the following rules:

• Let the construction order be $s$.
• For any $2 \le i \le n$, it must hold that skyscraper $s_i$ shares at least one common edge or a common corner with at least one previously built skyscraper.
• For any $1 \le i \le n$, it must hold that from the planned cell of skyscraper $s_i$ to the boundary of the 2D plane, there exists a path (you can move from one cell only to a cell that shares a common edge with it), and on this path there are no other skyscrapers except $s_i$.

An integer $t$ is also given, indicating the output type:

• If $t = 1$, you need to construct any valid construction order.
• If $t = 2$, you need to construct the construction order such that $(s_n, s_{n - 1}, \dots, s_1)$ is lexicographically largest.

Input Format

The first line contains an integer $n$.

The second line contains an integer $t$.

The next $n$ lines each contain two integers $r_i, c_i$. Line $i$ indicates that the planned coordinates of the $i$-th skyscraper are $(r_i, c_i)$.

Output Format

The first line outputs a string YES or NO, indicating whether a feasible solution exists.

If a feasible solution exists, then output $n$ lines, each with one integer describing the order you construct.

• If $t = 1$, you need to construct any valid construction order.
• If $t = 2$, you need to construct the construction order such that $(s_n, s_{n - 1}, \dots, s_1)$ is lexicographically largest.

3
2
0 0
0 1
0 2

YES
1
2
3

3
1
0 0
1 1
2 2

YES
2
3
1

2
1
0 0
0 2

NO

Hint

Sample Explanation

Sample 1 Explanation

These three skyscrapers form a line, so naturally there are the following solutions:

• $1, 2, 3$
• $2, 1, 3$
• $2, 3, 1$
• $3, 2, 1$

Because $t = 2$, output the first one.

Sample 2 Explanation

The only difference from Sample 1 is that the three skyscrapers form a diagonal line. The solutions are the same as in Sample 1, and since $t = 1$, output any one solution.

Sample 3 Explanation

The two skyscrapers do not touch each other, so it is naturally impossible to build them.

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 1.5 \times 10^5$, $1 \le t \le 2$, and $\lvert r_i \rvert, \lvert c_i \rvert \le 10^9$.

The detailed subtask constraints and scores are shown in the table below:

Notes

This problem is translated from Central-European Olympiad in Informatics 2019 Day 1 T1 Building Skyscrapers。

Translated by ChatGPT 5