Problem Description

You are given $n$ integer points on a 2D plane. It is guaranteed that for any integer $a$, there are at most two points of the form $(a, x)$; and for any integer $b$, there are at most two points of the form $(x, b)$.

You need to connect these $n$ points with $n/2$ line segments, such that each point is an endpoint of exactly one segment. The segments must be either horizontal or vertical, and they must not intersect.

Determine if this is possible. If it is, provide any valid configuration.

Input Format

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

Output Format

If it is not possible, output NE on a single line.

If it is possible, output DA on the first line. Then, for the next $n/2$ lines, output two integers each, representing the indices of the endpoints of a segment (indices start from 1).

Sample Input and Output

Sample Input #1

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

Sample Output #1

DA
1 5
3 7
2 6
4 8

Sample Input #2

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

Sample Output #2

DA
1 2
3 4
5 6

Sample Input #3

2
1 1
2 2

Sample Output #3

NE

Sample Input #4

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

Sample Output #4

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

Notes

Data Range

This problem is grouped tests.

• For $5$ points: $2 \leq n \leq 20$, and for any integer $a$, there are an even number of points of the form $(a, x)$ and an even number of points of the form $(x, a)$.
• For another $6$ points: $2 \leq n \leq 20$.
• For another $7$ points: $2 \leq n \leq 40$.
• For another $40$ points: $2 \leq n \leq 2000$.
• For all data: $2 \leq n \leq 100000$ and $1 \leq x_i, y_i \leq 100000$. For any integer $a$, there are at most $2$ points of the form $(a, x)$ and at most $2$ points of the form $(x, a)$.

Notes

Translated from COCI2019-2020 CONTEST #5 T3 Matching, translated by 90693.

SPJ by 90693, please contact privately or @ for any issues.

见题面 Input 部分

见题面 Output 部分