P6868 [COCI 2019/2020 #5] Matching

给你二维平面上的 $n$ 个整点。保证 $\forall a$，有至多两个形如 $(a,x)$ 的点；$\forall b$，有至多两个形如 $(x,b)$ 的点。 请你用 $n\over 2$ 条线段连接这 $n$ 个点。要求每个点都是一条线段的端点。要求这些线段都是水平的或竖直的。要求这些线段都不相交。 请你求出这是否可能。如果可能，请你输出任意一种方法。

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

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

### 数据范围 **本题捆绑测试。** - 对于 $5 pts$ 的数据：$2\leq n\leq 20$，且 $\forall a$ ，有偶数个形如 $(a,x)$ 的点和偶数个形如 $(x,a)$ 的点。 - 对于另外 $6 pts$ 的数据：$2\leq n\leq 20$。 - 对于另外 $7 pts$ 的数据：$2\leq n\leq 40$。 - 对于另外 $40 pts$ 的数据：$2\leq n\leq 2000$。 - 对于所有的数据：$2\leq n\leq 100000$ 且 $1\leq x_i,y_i\leq 100000$。对于任何整数 $a$ ，有至多 $2$ 个点 $(a,x)$ 和 至多 $2$ 个点 $(x,a)$。 ### 说明 **题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #5](https://hsin.hr/coci/archive/2019_2020/contest5_tasks.pdf) _T3 Matching_** ，译者 [90693](/user/90693)。 spj by [90693](/user/90693)，有任何问题请直接私信或@。