Patrol Robot

Ο Οργανισμός Ελέγχου Συντεταγμένων (Coordinate Control Organization) έχει αναπτύξει ένα αυτόνομο ρομπότ για να περιπολεί σε ~N~ διακριτές σημαντικές τοποθεσίες σε ένα δισδιάστατο επίπεδο. Η ~i~-οστή τοποθεσία έχει συντεταγμένες ~(x_i, y_i)~, και εγγυάται ότι δεν υπάρχουν τρεις τοποθεσίες που να βρίσκονται στην ίδια ευθεία.

Για να βοηθήσετε στην καθοδήγηση του ρομπότ, μπορείτε να βάψετε ορισμένα ευθύγραμμα τμήματα στο έδαφος. Κάθε τμήμα πρέπει να συνδέει απευθείας δύο σημαντικές τοποθεσίες και κανένα ζεύγος τμημάτων δεν επιτρέπεται να τέμνεται, εκτός ενδεχομένως στα άκρα τους.

Το ρομπότ θα ξεκινήσει την περιπολία του από το μέσο ενός αυθαίρετου τμήματος, κοιτάζοντας προς ένα από τα άκρα του. Θα κινείται επ' αόριστον σύμφωνα με την ακόλουθη διαδικασία:

• Όσο το ρομπότ βρίσκεται στο εσωτερικό ενός τμήματος, θα κινείται προς τα εμπρός, προς ένα από τα άκρα του.

• Όταν το ρομπότ φτάσει σε μια σημαντική τοποθεσία, αρχικά θα κοιτάζει ακριβώς προς την αντίθετη κατεύθυνση από το τμήμα που μόλις διέσχισε. Το ρομπότ θα στρίβει προς τα δεξιά, δηλαδή δεξιόστροφα, μέχρι η κατεύθυνση στην οποία κοιτάζει να ευθυγραμμιστεί με ένα τμήμα που οδηγεί μακριά από την τρέχουσα τοποθεσία. Στη συνέχεια, θα αρχίσει να κινείται κατά μήκος αυτού του νέου τμήματος.

Ο στόχος σας είναι να βάψετε τα τμήματα με τέτοιον τρόπο, ώστε, ανεξάρτητα από το σημείο εκκίνησης του ρομπότ, να είναι εγγυημένο ότι θα επισκέπτεται κάθε σημαντική τοποθεσία άπειρες φορές. Μπορεί να αποδειχθεί ότι αυτό είναι πάντα δυνατό.

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει έναν ακέραιο αριθμό ~N~ (~2 \le N \le 2000~), το πλήθος των σημαντικών τοποθεσιών.

Καθεμία από τις επόμενες ~N~ γραμμές περιέχει δύο ακέραιους αριθμούς ~x_i~ και ~y_i~, χωρισμένους με ένα κενό (~-10^9 \le x_i, y_i \le 10^9~), οι οποίοι είναι οι συντεταγμένες της ~i~-οστής σημαντικής τοποθεσίας.

Εγγυάται ότι και οι ~N~ σημαντικές τοποθεσίες είναι διαφορετικές και ότι δεν υπάρχουν τρεις που να βρίσκονται στην ίδια ευθεία.

Βαθμολογία

Βαθμοί	Επιπλέον περιορισμοί
~2~	~2 \le N \le 4~
~4~	~2 \le N \le 8~
~3~	~3 \le N~ και τα ~N~ σημεία είναι οι κορυφές ενός κυρτού πολυγώνου, με κάποια σειρά.
~7~	Τα ~N~ σημεία σχηματίζουν ένα κυρτό πολύγωνο με ~N-1~ κορυφές, καθώς και ένα επιπλέον σημείο στο εσωτερικό του πολυγώνου.
~9~	Κανένας επιπλέον περιορισμός.

Έξοδος

Στην πρώτη γραμμή, εκτυπώστε έναν θετικό ακέραιο αριθμό ~M~, το πλήθος των ευθύγραμμων τμημάτων που βάφετε στο έδαφος.

Καθεμία από τις επόμενες ~M~ γραμμές της εξόδου πρέπει να περιέχει δύο ακέραιους αριθμούς ~u_i~ και ~v_i~, χωρισμένους με ένα κενό (~1 \le u_i, v_i \le N~, ~u_i \ne v_i~), οι οποίοι δηλώνουν ότι βάφετε ένα ευθύγραμμο τμήμα μεταξύ της ~u_i~-οστής και της ~v_i~-οστής σημαντικής τοποθεσίας.

Αν υπάρχουν πολλές αποδεκτές απαντήσεις, μπορείτε να εκτυπώσετε οποιαδήποτε από αυτές.

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

input

4
0 0
1 1
1 2
2 1

output

3
1 2
2 3
2 4

Επεξήγηση του πρώτου παραδείγματος

Οι σημαντικές τοποθεσίες και τα τμήματα που βάφτηκαν φαίνονται στο παρακάτω σχήμα:

Ανεξάρτητα από το σημείο εκκίνησης του ρομπότ, αυτό θα επισκέπτεται κάθε σημαντική τοποθεσία άπειρες φορές.

Για παράδειγμα, αν το ρομπότ ξεκινήσει από το μέσο του τμήματος μεταξύ των τοποθεσιών 1 και 2, κοιτάζοντας προς την τοποθεσία 2, οι τοποθεσίες που θα επισκεφθεί με τη σειρά είναι:

~2, 4, 2, 3, 2, 1, 2, 4, \ldots~

όπου το υπογραμμισμένο τμήμα επαναλαμβάνεται άπειρες φορές.

input

8
0 0
0 3
1 1
1 2
4 1
4 2
5 0
5 3

output

9
1 2
2 4
4 8
8 7
7 5
5 1
3 4
4 5
5 6

Επεξήγηση του δεύτερου παραδείγματος

Οι σημαντικές τοποθεσίες και τα τμήματα που βάφτηκαν φαίνονται στο παρακάτω σχήμα:

Ανεξάρτητα από το σημείο εκκίνησης του ρομπότ, αυτό θα επισκέπτεται κάθε σημαντική τοποθεσία άπειρες φορές.

Για παράδειγμα, αν το ρομπότ ξεκινήσει από το μέσο του τμήματος μεταξύ των τοποθεσιών 4 και 5, κοιτάζοντας προς την τοποθεσία 5, οι τοποθεσίες που θα επισκεφθεί με τη σειρά είναι:

~5, 7, 5, 6, 5, 1, 2, 4, 3, 4, 8, 7, 5, \ldots~

όπου το υπογραμμισμένο τμήμα επαναλαμβάνεται άπειρες φορές. Σημειώστε ότι δεν είναι απαραίτητο να διασχίζεται κάθε τμήμα άπειρες φορές· η λύση είναι έγκυρη εφόσον κάθε τοποθεσία επισκέπτεται άπειρες φορές.