34912번 - Mahjong Connect 스페셜 저지다국어

문제

Busy Beaver has finally rage-quit Minesweeper and picked up Mahjong Connect instead. He has $N$ mahjong tiles at distinct locations on the Cartesian plane. Each tile $i$ has integer coordinates $(x_i, y_i)$ and a type $t_i$ with 1ドル \le t_i \le M$.

Two distinct tiles $i$ and $j$ match if and only if all of the following hold:

• They share the same type, i.e. $t_i=t_j$;
• They are on the same row or column, i.e. $x_i=x_j$ or $y_i=y_j$;
• They are not blocked by other types, i.e. every tile strictly between them in that row or column (if any) has the same type. Formally:
  • If $y_i=y_j,ドル then for every tile $k$ with $y_k=y_i$ and $\min\{x_i,x_j\}<x_k<\max\{x_i,x_j\},ドル we must have $t_k=t_i$;
  • If $x_i=x_j,ドル then for every tile $k$ with $x_k=x_i$ and $\min\{y_i,y_j\}<y_k<\max\{y_i,y_j\},ドル we must have $t_k=t_i$.

A perfect matching is a partition of the $N$ tiles into $N/2$ disjoint pairs such that every pair is a valid match under the rules above. Determine whether a perfect matching exists. If it does, output any one perfect matching; otherwise, report that no perfect matching exists.

입력

The first line contains two integers $N$ and $M$ (2ドル\le N\le 3\cdot 10^5,ドル 1ドル\le M\le 3\cdot 10^5,ドル $N$ is even).

The next $N$ lines describe the tiles. The $i$-th of these lines contains three integers $x_i,ドル $y_i$ and $t_i$ ($|x_i|,|y_i|\le 10^9,ドル 1ドル\le t_i\le M$).

It is guaranteed that the pairs $(x_i,y_i)$ are distinct.

출력

If no perfect matching exists, print a single line containing NO.

Otherwise, print a single line containing YES. Then print $N/2$ lines, each containing two integers $i$ and $j$ (1ドル\le i,j\le N,ドル $i\neq j$), indicating that tiles $i$ and $j$ form a matched pair.

Each index from 1ドル$ to $N$ must appear in exactly one pair. The pairs may be printed in any order, and within each pair, the order of $i$ and $j$ does not matter.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

제한

노트

In the first test case, we can pair up the tiles at $(-1,0),(1,0)$ and $(0,-1),(0,1),ドル respectively.

In the second test case, we cannot do the same thing because the tile at $(0,0)$ blocks the connection between $(-1,0)$ and $(1,0)$.

The visualization of the third test case is as follows (different colors represent different types of tiles):

Note again that, if the answer is YES, any valid pairing with any order will be accepted. For instance, for the first sample, the following output is also acceptable:

YES
4 3
1 2