You are given $N$, where $N$ is even, points on a plane that have integer coordinates. For each integer $a$, there are at most two points with coordinates $(a,x)$. Analogously, for each integer $b$, there are at most two points with coordinates $(x,b)$.

You are able to draw horizontal or vertical line segments between pairs of given points. Is it possible to draw $\frac{N}{2}$ lines such that each of the given points is an endpoint of exactly one line segment and that no two line segments intersect?

Input

The first line contains an even integer $N$ $(2\le N\le 100000)$ from the task description. The $i$-th of the next $N$ lines contains two integers $X_i,Y_i$ $(1\le X_i,Y_i\le 100000)$, coordinates of the $i$-th point.

Output

If it is not possible to draw the line segments as explained in the task statement, you should output NE (NO in Croatian) in a single line.

Otherwise, you should output DA (YES in Croatian) in the first line. In each of the next $\frac{N}{2}$ lines you should output two space-separated integers $i$ and $j$ $(1\le i,j\le N)$, which represent indices of the points that are connected with a drawn line segment.

Scoring

Subtask	Score	Constraints
$1$	$5$	$2\le N\le 20$, for each integer $a$, there is an even number of points with coordinates $(a,x)$ and an even number of points with coordinates $(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$	No additional constraints.

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