문제
2차원 평면 상에 N(N은 짝수)개의 점들이 주어진다.
모든 점들에 대하여 같은 x좌표를 갖는 점들은 최대 2개이며, 같은 y좌표를 갖는 점들은 최대 2개이다.
N/2개의 수직, 수평 선분들을 이용하여 점들을 2개씩 이어주었을 때 어떠한 두 선분도 겹치지 않게 할 수 있는가?
입력
짝수인 정수 N (2 ≤ N ≤ 100 000) 이 주어진다.
이후 N개의 줄에 각 점의 좌표를 의미하는 정수 Xi, Yi (1 ≤ Xi, Yi ≤ 100 000) 가 주어진다. 어떠한 두 점도 겹치지 않음이 보장된다.
출력
조건을 만족하는 선분들을 만들 수 없다면 "NE"를 출력한다. (큰따옴표 제외)
조건을 만족하는 선분들을 만들 수 있다면 "DA"를 출력한다. (큰따옴표 제외)
다음 N/2개 줄에는 공백으로 구분하여 선분으로 연결할 두 점의 번호 i, j를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 5점 | 2 ≤ N ≤ 20, 모든 정수 a에 대하여 (a, x) 의 형태의 점들과 (x, a) 형태의 점들은 짝수개임이 보장된다. |
| #2 | 6점 | 2 ≤ N ≤ 20 |
| #3 | 7점 | 2 ≤ N ≤ 40 |
| #4 | 32점 | 2 ≤ N ≤ 2000 |
| #5 | 50점 | 추가 제한조건 없음 |
예제1
입력
8
11
13
22
24
31
33
42
44
출력
DA
15
37
26
48
예제2
입력
6
12
13
21
24
32
33
출력
DA
12
34
56
예제3
입력
2
11
22
출력
NE
출처
COCI 2019/2020 Contest 5