Totem

Ο Κύριος Νο (πραγματικό όνομα Jerry Drake) είναι ένας χαρακτήρας κόμικ που μπλέκει συχνά σε πολλά προβλήματα, από τα οποία συνήθως μπορεί να ξεφύγει. Ωστόσο, αυτή τη φορά δεν είναι τόσο εύκολο. Έψαχνε για αρχαίους θησαυρούς των Μάγια και, στην πορεία, έπεσε πάνω σε έναν χαμένο ναό. Μέσα στο ναό υπάρχει μια μεγάλη αίθουσα, και μέσα στην αίθουσα στέκεται ένα πέτρινο τοτέμ με επιγραφές που είναι το κλειδί για την κατανόηση του σκοπού της ζωής (42). Ωστόσο, το να φτάσετε στο Τοτέμ είναι μια μεγάλη πρόκληση. Το Τοτέμ βρίσκεται στην απέναντι πλευρά της αίθουσας από την είσοδο. Το δάπεδο της αίθουσας είναι καλυμμένο με πέτρινα πλακάκια που μοιάζουν πολύ με πλακάκια ντόμινο. Κάθε πλακίδιο χωρίζεται σε δύο μισά (τετράγωνα) και κάθε μισό έχει έναν αριθμό από ένα έως και έξι, λαξευμένο μέσα του. Τα πλακίδια είναι διατεταγμένα σε ~N~ σειρές, με ~N~ πλακίδια σε κάθε σειρά με περιττό αριθμό και ~N - 1~ πλακίδια σε κάθε σειρά με ζυγό αριθμό. Η παρακάτω εικόνα αντιστοιχεί στο πρώτο παράδειγμα δοκιμής ~(N = 5)~:

Είναι δυνατή η μετάβαση από ένα πλακίδιο σε ένα διπλανό μόνο εάν τα δύο πλακίδια έχουν αντίστοιχους αριθμούς στα μισά που μοιράζονται μια πλευρά. Βοηθήστε τον κ. No να βρει τη συντομότερη διαδρομή προς το Τοτέμ, προσδιορίζοντας τη σειρά των πλακιδίων (αναφέροντας την ακολουθία των ετικετών των πλακιδίων, που περιγράφεται παρακάτω) που πρέπει να πατηθούν, με τη σειρά, από το πρώτο έως το τελευταίο πλακίδιο στη διαδρομή. Εάν δεν υπάρχει πιθανό μονοπάτι για το Τοτέμ, βρείτε το συντομότερο μονοπάτι προς το πλακίδιο με τη μεγαλύτερη ετικέτα (ώστε ο κύριος No να κάνει ένα ηρωικό άλμα). Τα πέτρινα πλακίδια επισημαίνονται σύμφωνα με τη σειρά : στην πρώτη σειρά, το πρώτο πλακίδιο έχει την ετικέτα 1 και το τελευταίο ~N~. στη δεύτερη σειρά, το πρώτο πλακίδιο είναι ~N + 1~ και το τελευταίο ~2*N - 1~ και ούτω καθεξής. Η είσοδος οδηγεί στο πλακίδιο με την ετικέτα 1 και το τοτέμ βρίσκεται στο τελευταίο πλακίδιο της τελευταίας σειράς. Ο κύριος No ξεκινά πάντα από την είσοδο.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~N~ ~(1 \le N \le 500)~, τον αριθμό των σειρών πέτρινων πλακιδίων.
Καθεμία από τις ακόλουθες γραμμές ~N \times N - N/2~ (όπου το / σημαίνει διαίρεση ακεραίων) περιέχει δύο θετικούς ακέραιους ~A_i~ και ~B_i~ ~(1 \le A_i, B_i \le 6,\;1 \le i \le N \times N - N/2)~, οι τιμές κομμένες στο αριστερό και το δεξί μισό, αντίστοιχα, του πλακιδίου ~i~.

Έξοδος

Η πρώτη γραμμή εξόδου πρέπει να περιέχει το μήκος (σε πλακίδια) της απαιτούμενης συντομότερης διαδρομής.
Η δεύτερη γραμμή εξόδου πρέπει να περιέχει μια ακολουθία θετικών ακεραίων χωρισμένων με διάστημα, τις ετικέτες των πλακιδίων στη συντομότερη διαδρομή. Καθώς μπορεί να υπάρχουν περισσότερα από ένα συντομότερα μονοπάτια, τυπώστε οποιοδήποτε από αυτά.

Βαθμολογία

Εάν μόνο η πρώτη γραμμή εξόδου είναι σωστή, η λύση λαμβάνει το ~50~% των πόντων για αυτήν την περίπτωση δοκιμής.

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

input

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

output

7
1 2 7 12 17 22 23

input

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

output

4
1 2 5 8

input

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

output

7
1 5 8 12 9 10 13