Trên một mặt phẳng, cho ~N~ chẵn điểm có toạ độ nguyên. Với mỗi một số nguyên ~a~ có nhiều nhất ~2~ điểm có toạ độ ~(a,x)~. Tương tự như vậy, với mỗi số nguyên ~b~, có nhiều nhất ~2~ điểm có toạ độ ~(x, b)~.

Bạn được phép vẽ các đoạn thẳng theo chiều ngang (giữa một cặp điểm có cùng tung độ) hoặc chiều dọc (giữa một cặp điểm có cùng hoành độ). Hãy xác định xem việc vẽ ~\frac{N}{2}~ đoạn thẳng sao cho mỗi điểm trên mặt phẳng là đầu mút của duy nhất một đoạn thẳng và không có ~2~ đoạn thẳng nào cắt nhau có khả thi hay không?

Input

• Dòng đầu chứa số nguyên chẵn ~N~ ~(2 ≤ N ≤ 100000)~.

• Dòng thứ ~i~ của ~N~ dòng tiếp theo chứa ~2~ số nguyên ~X_i~, ~Y_i~ với ~(1 ≤ X_i, Y_i ≤ 100 000)~ đại diện cho toạ độ của điểm thứ ~i~ trên mặt phẳng.

Output

• In NE (nghĩa là Không trong tiếng Croatia) nếu như không thể vẽ theo yêu cầu của đề bài.

• Nếu ngược lại, in DA (nghĩa là Có trong tiếng Croatia) ở dòng đầu tiên. Ở ~\frac{N}{2}~ dòng tiếp theo, mỗi dòng in ~2~ số nguyên ~i~, ~j~ phân cách nhau bởi dấu cách, với ~i~ và ~j~ ~(1 ≤ i, j ≤ N)~ là số thứ tự hai điểm đầu mút của đoạn thẳng được vẽ.

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

Subtask

• Subtask ~1~: ~2~ test có ~2 \le N \le 20~ với mỗi số nguyên ~a~, tồn tại một số chẵn điểm với toạ độ ~(a,x)~ và một số chẵn điểm với toạ độ ~(x,a)~
• Subtask ~2~: ~5~ test có ~2 \le N \le 20~
• Subtask ~3~: ~5~ test có ~2 \le N \le 40~
• Subtask ~4~: ~12~ test có ~2 \le N \le 2000~
• Subtask ~5~: ~14~ test còn lại không có điều kiện gì thêm