第 4 题 Matching (matching)

本题使用文件输入输出：输入文件 matching.in，输出文件 matching.out。

题目描述

给你二维平面上的 $n$ 个整点。保证 $\forall a$，有至多两个形如 $(a, x)$ 的点；$\forall b$，有至多两个形如 $(x, b)$ 的点。

请你用 $\frac{n}{2}$ 条线段连接这 $n$ 个点。要求每个点都是一条线段的端点。要求这些线段都是水平的或竖直的。要求这些线段都不相交。

请你求出这是否可能。如果可能，请你输出任意一种方法。

输入格式

• 第一行有一个偶正整数 $n$。
• 接下来有 $n$ 行。第 $i$ 行有两个正整数 $x_i, y_i$，表示第 $i$ 个点的坐标。

输出格式

如果不可能，请在一行输出 NE。

如果可能，请在第一行输出 DA。在接下来的 $\frac{n}{2}$ 行中各输出两个整数，表示一条线段（整数是端点的编号，从 1 开始）。

样例

样例 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

样例 2

输入：

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

输出：

DA
1 2
3 4
5 6

样例 3

输入：

2
1 1
2 2

输出：

NE

样例 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

输出：

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

提示

数据范围

本题捆绑测试。

• 对于 5pts 的数据：$2 \le n \le 20$，且 $\forall a$，有偶数个形如 $(a, x)$ 的点和偶数个形如 $(x, a)$ 的点。
• 对于另外 6pts 的数据：$2 \le n \le 20$。
• 对于另外 7pts 的数据：$2 \le n \le 40$。
• 对于另外 40pts 的数据：$2 \le n \le 2000$。
• 对于所有的数据：$2 \le n \le 100000$ 且 $1 \le x_i, y_i \le 100000$。对于任何整数 $a$，有至多 2 个点 $(a, x)$ 和至多 2 个点 $(x, a)$。

说明

spj by 90693，有任何问题请直接私信或@。