Vera and Trail Building

Η Vera λατρεύει την πεζοπορία και πρόκειται να φτιάξει το δικό της δίκτυο μονοπατιών. Θα αποτελείται από ~V~ τοποθεσίες αριθμημένες από το ~1~ έως το ~V~ και ~E~ αμφίδρομα μονοπάτια όπου το ~i~-οστο μονοπάτι ενώνει απευθείας δύο διακριτές τοποθεσίες ~a_i~ και ~b_i~. Η Vera θα ήθελε το δίκτυό της να είναι συνδεδεμένο, επομένως θα πρέπει να είναι δυνατή η πεζοπορία μεταξύ δύο οποιωνδήποτε τοποθεσιών με τη χρήση των μονοπατιών. Είναι πιθανό να υπάρχουν περισσότερα από ένα μονοπάτια που ενώνουν απευθείας το ίδιο ζευγάρι τοποθεσιών.

Η Vera θεωρεί πως δύο τοποθεσίες ~a~, ~b~ με ~a < b~ σχηματίζουν ένα όμορφα συνδεδεμένο ζεύγος αν είναι εφικτό να περπατήσεις χρησιμοποιώντας τα μονοπάτια από το ~a~ στο ~b~ και πάλι πίσω χωρίς να περάσεις από το ίδιο μονοπάτι πάνω από μία φορά. Πιστεύει πως το δίκτυο μονοπατιών της θα ήταν όμορφο αν είχε ~K~ ακριβώς όμορφα συνδεδεμένα ζεύγη.

Η Vera δεν θέλει το δίκτυό της να είναι πολύ μεγάλο, οπότε το δίκτυο θα πρέπει να ικανοποιεί την ανίσωση ~1 \le V, E \le 5\,000~.

Δεδομένου του ~K~, βοηθήστε τη Vera να βρει ένα όμορφο δίκτυο μονοπατιών.

Είσοδος

Υπάρχει μόνο μία γραμμή εισόδου, η οποία περιέχει τον ακέραιο ~K~ (~0 < K \le 10^7~).

Βαθμολογία

Για ~3~ από τους ~25~ διαθέσιμους βαθμούς, ~K \le 1\,000~.

Για επιπλέον ~6~ από τους ~25~ διαθέσιμους βαθμούς, ~K \le 10^5~.

Έξοδος

Εκτυπώστε ένα όμορφο δίκτυο με την ακόλουθη μορφή:

• η πρώτη γραμμή θα πρέπει να περιέχει τον αριθμό των κορυφών ~V~, ακολουθούμενο από ένα κενό, ακολουθούμενο από τον αριθμό των άκρων, ~E~

• καθεμία από τις επόμενες ~E~ γραμμές θα πρέπει να περιέχει δύο ακέραιους ~a_i~ και ~b_i~, χωρισμένους με ένα κενό, που υποδεικνύουν ένα μονοπάτι μεταξύ των τοποθεσιών ~a_i~ και ~b_i~ (~1 \le i \le E~).

Τα μονοπάτια μπορούν να εκτυπωθούν με οποιαδήποτε σειρά. Οι δύο τοποθεσίες οποιουδήποτε μονοπατιού μπορούν να εκτυπωθούν με οποιαδήποτε σειρά. Αν υπάρχουν πολλαπλά όμορφα δίκτυα μονοπατιών, εκτυπώστε οποιοδήποτε από αυτά. Είναι εγγυημένο ότι υπάρχει πάντα λύση.

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

input

2

output

4 5
1 2
2 1
3 4
4 3
1 4

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

Τα δύο όμορφα συνδεδεμένα ζεύγη είναι το ~1~, ~2~ και ~3~, ~4~.

input

6

output

4 4
1 2
2 3
3 4
4 1

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

Όλα τα ζεύγη τοποθεσιών σχηματίζουν ένα όμορφα συνδεδεμένο ζεύγος.