Hiperkocka

...it's dark in the cube, it's dark in the cube...

Πέντε το πρωί. Ο Ντάνιελ ξυπνά, ανοίγει τα μάτια του. Το κεφάλι του πονάει λίγο. Μπορεί ακόμα να ακούσει το κουδούνισμα στα αυτιά του.

...I was in the cube, I was in the cube...

Θυμάται μια παρόμοια κατάσταση στην οποία βρέθηκε, πριν από τρία χρόνια, στον διαγωνισμό COCI, στον γύρο 2, με το πρόβλημα Kocka.

...I'm in the cube again, I'm in the cube again...

Αλλά αυτή τη φορά, τα πράγματα είναι πολύ πιο περίπλοκα... Ο Ντάνιελ βρίσκεται σε έναν υπερκύβο n διαστάσεων ~Q_n~. \(2^{n - 1)\) πανομοιότυπα αντίγραφα ενός δέντρου T με n άκρες είναι διάσπαρτα γύρω του. Σύντομα του γίνεται ξεκάθαρο ότι η σωτηρία έγκειται στην πλακόστρωση των ακμών του υπερκύβου με τα δέντρα.

Επίσημα, ένας υπερκύβος ~Q_n~ είναι ένας γράφος με κόμβους ~0,\;1,\;\ldots,\;2_n - 1~, στον οποίο οι κόμβοι ~x~ και ~y~ συνδέονται αν και μόνο αν το δυαδικό αποτέλεσμα της xor (bitwise xor) τους είναι δύναμη του δύο.

Ένα δέντρο μπορεί να τοποθετηθεί στον υπερκύβο έτσι ώστε:

• κάθε κόμβος του δέντρου να αντιστοιχεί σε κάποιο κόμβο του υπερκύβου

• αυτοί οι κόμβοι πρέπει να είναι διακριτοί

• εάν υπάρχει μια ακμή μεταξύ δύο κόμβων στο δέντρο, τότε πρέπει να υπάρχει μια ακμή μεταξύ των αντίστοιχων κόμβων στον υπερκύβο.

Η πλακόστρωση του υπερκύβου γίνεται με την τοποθέτηση πολλών δέντρων έτσι ώστε κάθε ακμή του υπερκύβου να ανήκει το πολύ σε ένα δέντρο.

Ο στόχος σας είναι να καλύψετε τον υπερκύβο ~Q_n~ με όσο περισσότερα αντίγραφα του δεδομένου δέντρου T, το οποίο έχει n ακμές.

Είσοδος

Η πρώτη γραμμή περιέχει έναν θετικό ακέραιο ~n\;(1 \le n \le 16)~, τη διάσταση του υπερκύβου.

Καθεμία από τις ακόλουθες n γραμμές περιέχει δύο ακέραιους αριθμούς ~x~ και ~y\;(0 \le x, y \le n,\;x \ne y)~, που δηλώνουν ότι οι κόμβοι ~x~ και ~y~ συνδέονται με μια ακμή στο δέντρο T.

Έξοδος

Στην πρώτη γραμμή εκτυπώστε τον αριθμό των δέντρων στην πλακόστρωσή σας.

Κάθε μία από τις ακόλουθες γραμμές πρέπει να περιγράφει την τοποθέτηση ενός αντιγράφου του δέντρου T .

Στην ~i~-οστή γραμμή εκτυπώστε ~n + 1~ αριθμούς ~a_0^{(i)},\;a_1^{(i)},\;\ldots,a_n^{(i)}~. Αυτοί οι αριθμοί δηλώνουν ότι το ~i~-οστό δέντρο τοποθετείται έτσι ώστε ο κόμβος του υπερκύβου ~a_j^{(i)}~ να αντιστοιχεί στον κόμβο δέντρου ~j~, για κάθε ~j = 0,\;\ldots,\;n~.

Βαθμολογία

Εάν η λύση σας τοποθετεί σωστά ~k~ δέντρα, θα λάβετε ~f(k) \cdot 110~ βαθμούς για αυτήν την περίπτωση δοκιμής, όπου

$$\displaystyle f(k) = \begin{cases} 0.7\cdot k/2^{n-1} & \text{αν } & k<2^{n-1} \\ 1 & \text{αν } & k=2^{n-1}. \\ \end{cases}$$

Φυσικά, εάν η λύση σας δεν είναι σωστή, θα λάβετε 0 βαθμούς.

Ο συνολικός αριθμός των πόντων σας είναι ίσος με τον ελάχιστο αριθμό πόντων που λαμβάνει η λύση σας σε όλες τις δοκιμαστικές περιπτώσεις.

Είναι δυνατό να αποδειχθεί ότι υπάρχει πάντα μια λύση που χρησιμοποιεί όλα τα ~2^{n - 1}~ δέντρα.

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

input

1
0 1

output

1
0 1

input

2
0 1
1 2

output

2
0 1 3
0 2 3

input

3
0 1
0 2
0 3

output

4
0 1 2 4
3 1 2 7
5 1 4 7
6 2 4 7

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