Matching

Σας δίνονται ~N~ (~N~ άρτιος) σημεία σε ένα επίπεδο που έχουν ακέραιες συντεταγμένες. Για κάθε ακέραιο ~a~, υπάρχουν το πολύ δύο σημεία με συντεταγμένες ~(a, x)~. Ανάλογα, για κάθε ακέραιο ~b~, υπάρχουν το πολύ δύο σημεία με συντεταγμένες ~(x, b)~.

Μπορείτε να σχεδιάσετε οριζόντια ή κάθετα τμήματα γραμμής μεταξύ ζευγών δεδομένων σημείων. Eίναι δυνατόν να σχεδιάστε ~\frac{N}{2}~ γραμμές έτσι ώστε κάθε ένα από τα δεδομένα σημεία να αποτελεί τελικό σημείο ενός μόνο ευθύγραμμου τμήματος και ότι οποιαδήποτε δύο ευθύγραμμα τμήματα δέν τέμνονται;

Είσοδος

Η πρώτη γραμμή περιέχει έναν ζυγό ακέραιο ~N\;(2 \le N \le 100\,000)~.

Η i-οστή των επόμενων ~N~ ευθειών περιέχει δύο ακέραιους αριθμούς ~X_i,\;Y_i\;(1 \le X_i, Y_i \le 100\,000)~, συντεταγμένες του i-οστού σημείου.

Έξοδος

Εάν δεν είναι δυνατό να σχεδιάσετε τα τμήματα γραμμής όπως εξηγείται παραπάνω, θα πρέπει να τυπώσετε "NE" (το "ΟΧΙ" στα κροατικά) σε μία μόνο γραμμή.

Διαφορετικά, θα πρέπει να τυπώσετε "DA" (ΝΑΙ στα Κροατικά) στην πρώτη γραμμή. Σε κάθε μία από τις επόμενες γραμμές ~\frac{N}{2}~ εσείς θα πρέπει να τυπώσετε δύο ακέραιους αριθμούς ~i~ και ~j\;(1 \le i, j \le N)~, οι οποίοι αντιπροσωπεύουν δείκτες των σημείων που συνδέονται με τραβηγμένο ευθύγραμμο τμήμα.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	5	~2 \le N \le 20~, για κάθε ακέραιο ~a~, υπάρχει ένας ζυγός αριθμός σημείων με συντεταγμένες ~(a, x)~ και ένας ζυγός αριθμός σημείων με συντεταγμένες ~(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	Χωρίς πρόσθετους περιορισμούς

Παραδείγματα

input

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

output

DA
1 5
3 7
2 6
4 8

input

6
1 2
1 3
2 1
2 4
3 2
3 3

output

DA
1 2
3 4
5 6

input

2
1 1
2 2

output

NE