Problem Description

In a 2D plane, there are $n$ grids planned for building skyscrapers, with the $i$-th planned skyscraper located at $(r_i, c_i)$.

You can choose any order to build the skyscrapers, but it must satisfy the following conditions:

• Let the building order be $s$.
• For any $2 \le i \le n$, the $s_i$-th skyscraper must share at least one edge or corner with any of the previously built skyscrapers.
• For any $1 \le i \le n$, there must be a path from the grid of the $s_i$-th planned skyscraper to the boundary of the 2D plane (a path can only move to a grid sharing an edge), and no other skyscrapers should be on this path except the $s_i$-th skyscraper.

Additionally, an integer $t$ will be given indicating the type of output:

• If $t = 1$, you need to construct any valid building order.
• If $t = 2$, you need to construct the building order with the largest lexicographical order $(s_n, s_{n-1}, \dots, s_1)$.

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$ and $c_i$, indicating the coordinates of the $i$-th planned skyscraper.

Output Format

The first line should be a string YES or NO, indicating whether there is a feasible solution.

If there is a feasible solution, the next $n$ lines should each contain an integer representing the constructed order.

• If $t = 1$, you need to construct any valid building order.
• If $t = 2$, you need to construct the building order with the largest lexicographical order $(s_n, s_{n-1}, \dots, s_1)$.

Sample Input and Output

Input Sample #1

3
2
0 0
0 1
0 2

Output Sample #1

YES
1
2
3

Input Sample #2

3
1
0 0
1 1
2 2

Output Sample #2

YES
2
3
1

Input Sample #3

2
1
0 0
0 2

Output Sample #3

NO

Notes/Hints

Sample Explanation

Sample 1 Explanation

These three skyscrapers are in a line, naturally having the following solutions:

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

Since $t = 2$, the first solution is output.

Sample 2 Explanation

The difference from Sample 1 is that the three skyscrapers are in a diagonal line, with the same solutions as Sample 1. Since $t = 1$, any solution can be output.

Sample 3 Explanation

The two skyscrapers do not intersect, so they cannot be built.

Data Range

For $100\%$ of the data, 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$.

Detailed subtask constraints and scores are as follows:

Notes

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

见题面 Input 部分

见题面 Output 部分