P6868 [COCI 2019/2020 #5] Matching

You are given $n$ lattice points on a 2D plane. It is guaranteed that for any $a$, there are at most two points of the form $(a,x)$; and for any $b$, there are at most two points of the form $(x,b)$. You need to connect these $n$ points using ${n \over 2}$ line segments. Each point must be an endpoint of exactly one segment. All segments must be horizontal or vertical. Also, no two segments may intersect. Determine whether this is possible. If it is, output any valid way.

- The first line contains an even positive integer $n$. - The next $n$ lines follow. The $i$-th line contains two positive integers $x_i, y_i$, representing the coordinates of the $i$-th point.

If it is impossible, output `NE` in one line. If it is possible, output `DA` in the first line. In the next ${n \over 2}$ lines, output two integers for each line segment (the integers are the indices of its endpoints, starting from $1$).

### Constraints **This problem uses bundled testdata.** - For $5 pts$ of the testdata: $2\leq n\leq 20$, and for all $a$, there is an even number of points of the form $(a,x)$ and an even number of points of the form $(x,a)$. - For another $6 pts$ of the testdata: $2\leq n\leq 20$. - For another $7 pts$ of the testdata: $2\leq n\leq 40$. - For another $40 pts$ of the testdata: $2\leq n\leq 2000$. - For all testdata: $2\leq n\leq 100000$ and $1\leq x_i, y_i\leq 100000$. For any integer $a$, there are at most $2$ points $(a,x)$ and at most $2$ points $(x,a)$. ### Notes **Translated from [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #5](https://hsin.hr/coci/archive/2019_2020/contest5_tasks.pdf) _T3 Matching_**, translator: [90693](/user/90693). SPJ by [90693](/user/90693). If you have any questions, please send a private message or @ them. Translated by ChatGPT 5