给定平面上 $N$ 个具有整数坐标的点，其中 $N$ 为偶数。对于每个整数 $a$，坐标为 $(a, x)$ 的点最多有两个。同理，对于每个整数 $b$，坐标为 $(x, b)$ 的点最多有两个。
你可以在给定的点对之间绘制水平或垂直的线段。是否可以绘制 $\frac{N}{2}$ 条线段，使得每个给定的点恰好是其中一条线段的一个端点，且任意两条线段都不相交？
输入格式
第一行包含一个偶数 $N$（$2 \le N \le 100\,000$），表示点的数量。
接下来的 $N$ 行中，第 $i$ 行包含两个整数 $X_i, Y_i$（$1 \le X_i, Y_i \le 100\,000$），表示第 $i$ 个点的坐标。
输出格式
如果无法按照题目要求绘制线段，应在单行中输出 "NE"（克罗地亚语中的“否”）。
否则，第一行输出 "DA"（克罗地亚语中的“是”）。在接下来的 $\frac{N}{2}$ 行中，每行输出两个空格分隔的整数 $i$ 和 $j$（$1 \le i, j \le N$），表示由绘制的线段连接的点的索引。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 5 | $2 \le N \le 20$，且对于每个整数 $a$，坐标为 $(a, x)$ 的点有偶数个，且坐标为 $(x, a)$ 的点也有偶数个。 |
| 2 | 6 | $2 \le N \le 20$ |
| 3 | 7 | $2 \le N \le 40$ |
| 4 | 40 | $2 \le N \le 2000$ |
| 5 | 52 | 无附加限制。 |
样例
输入样例 1
8 1 1 1 3 2 2 2 4 3 1 3 3 4 2 4 4
输出样例 1
DA 1 5 3 7 2 6 4 8
输入样例 2
6 1 2 1 3 2 1 2 4 3 2 3 3
输出样例 2
DA 1 2 3 4 5 6
输入样例 3
2 1 1 2 2
输出样例 3
NE