题目描述

译自 COCI 2019/2020 Contest #5 T3「Matching」

给定一个偶数 $N$，表示二维平面上有 $N$ 个整点（整点即点坐标均为整数的点）。对于每个整数 $a$，最多有两个点坐标为 $(a,x)$，类似地，对于每个整数 $b$，最多有两个点坐标为 $(x,b)$。

你可以在两点之间画一条竖直或水平的线段，请问是否可能画出 $\frac{N}{2}$ 条线段，使得每个给出的点都是恰好一条线段的一个端点，且线段之间两两不相交。

输入格式

第一行一个整数 $N$，意义如题目描述；

接下来 $N$ 行，每行两个整数 $X_i,Y_i$，表示第 $i$ 个点的坐标。

输出格式

如果不能按题目描述的规定划线，则在第一行输出 NE（克罗地亚语中的「否」）。

否则第一行输出 DA（克罗地亚语中的「是」）。在接下来的 $\frac{N}{2}$ 行，每行输出两个整数 $i,j$，用一个空格隔开，表示 $i,j$ 两个点间画一条线段。

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

数据范围与提示

对于所有数据，$2\le N\le 10^5,1\le X_i,Y_i\le 10^5$。

详细子任务附加限制及分值如下：