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 ^{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?

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.

The first line contains an even integer \(N\) (\(2 \le N \le 100\,000\)) from the task description.
The \(i-th\) of the next \(N\) lines contains two integers \(X@@RISE_MATH_BLOCK_0@@i\) (\(1 \le X\)\(i\), Y\(i \le 100\,000\)), coordinates of the \(i-th\)
point.

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 ^{N}
_{2} ^{lines} ^{you}
should output two spa\(ce-se\)parated integers \(i\) and \(j\) (\(1 \le i\), \(j \le N\)), which represent indices of the points
that are connected with a drawn line segment.

생성자가 기록되지 않았습니다.

출처 COCI 2019/2020 Contest 5