Bạn được cho ~N~ điểm trên mặt phẳng, với tọa độ nguyên, và ~N~ là số chẵn. Với mỗi số nguyên ~a~, có tối đa hai điểm với tọa độ ~(a, x)~. Tương tự, với mỗi số nguyên ~b~, có tối đa hai điểm với tọa độ ~(x, b)~.

Bạn có khả năng vẽ các đoạn thẳng ngang hoặc dọc giữa các cặp điểm đã cho. Liệu có thể vẽ ~\frac{N}{2}~ đường thẳng sao cho mỗi điểm đã cho là điểm cuối của đúng một đoạn thẳng và không có hai đoạn thẳng nào cắt nhau không?

Input

• Dòng đầu tiên chứa một số nguyên chẵn ~N~ ~(2 \leq N \leq 100 000)~ từ mô tả bài toán.
• Mỗi dòng thứ ~i~ trong ~N~ dòng tiếp theo chứa hai số nguyên ~X_i, Y_i~ ~(1 \leq X_i, Y_i \leq 100 000)~, là tọa độ của điểm thứ ~i~.

Output

• Nếu không thể vẽ các đoạn thẳng như đã giải thích, bạn cần xuất ~NE~ (NO trong tiếng Croatia) trong một dòng.
• Nếu có thể, bạn cần xuất ~DA~ (YES trong tiếng Croatia) trong dòng đầu tiên. Trong mỗi dòng tiếp theo của ~\frac{N}{2}~ dòng, bạn cần xuất hai số nguyên cách nhau bởi khoảng trắng ~i và ~j~ ~(1 \leq i, j \leq N)~, đại diện cho chỉ số của các điểm được kết nối bởi đoạn thẳng đã vẽ.

Chú ý

• Subtask 1: 5 điểm với ~2 \leq N \leq 20~, với mỗi số nguyên ~a~, có một số chẵn điểm với tọa độ ~(a, x)~ và một số chẵn điểm với tọa độ ~(x, a)~.
• Subtask 2: 6 điểm với ~2 \leq N \leq 20~.
• Subtask 3: 7 điểm với ~2 \leq N \leq 40~.
• Subtask 4: 40 điểm với ~2 \leq N \leq 2000~.
• Subtask 5: 52 điểm không có ràng buộc thêm.

Sample Input 1

8
1 1
1 3
2 2
2 4
3 1
3 3
4 2
4 4

Sample Ouput 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 Ouput 2

DA
1 2
3 4
5 6

Sample Input 3

2
1 1
2 2

Sample Ouput 3

NE