Description

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.

Input Format

• 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.

Output Format

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$).

8
1 1
1 3
2 2
2 4
3 1
3 3
4 2
4 4

DA
1 5
3 7
2 6
4 8

6
1 2
1 3
2 1
2 4
3 2
3 3

DA
1 2
3 4
5 6

2
1 1
2 2

NE

20
62488 5330
62488 5027
76436 5027
39827 79374
95732 59715
66222 46366
8346 59715
49581 53207
66222 79374
80123 46366
76436 5330
39590 5690
82990 89723
95732 89723
8346 79295
80123 16069
39827 16069
49581 5690
82990 79295
39590 53207

DA
3 11
1 2
16 10
6 9
4 17
13 19
15 7
5 14
12 20
8 18

Hint

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 CONTEST #5 T3 Matching, translator: 90693.

SPJ by 90693. If you have any questions, please send a private message or @ them.

Translated by ChatGPT 5