Izlet

Όταν ένας ανταγωνιστικός προγραμματιστής σκέφτεται ένα δέντρο, δεν είναι το ίδιο δέντρο που σκέφτεται ένας απλός άνθρωπος. Ευτυχώς, σε αυτό τo πρόβλημα, και οι δύο έννοιες είναι σωστές.
Ο Nikola λατρεύει τη φύση και συχνά περπατά στο δάσος, κοιτάζοντας τα δέντρα και θαυμάζοντας το μέγεθός τους, τους βαθμούς των κόμβων τους, την παραδόξως τακτική τυχαιότητα κ.λπ. Αυτή τη μέρα της υπέροχης άνοιξης, υπάρχουν ακόμη περισσότεροι λόγοι για να κοιτάξουμε πάνω σε αυτά τα υπέροχα πλάσματα: τα δέντρα είναι γεμάτα χρώμα και αυτό αιχμαλώτισε την προσοχή του Nikola.
Μια μέρα λοιπόν παρατήρησε ένα μεγάλο δέντρο με ~N~ κόμβους, βλέποντας ένα χρώμα σε κάθε κόμβο. Υπήρχε ένα λουλούδι, ένα ζώο, ή ο Nikola απλά τρελάθηκε, είναι δύσκολο να πεις. Αλλά κοίταζε αυτό το δέντρο για πολλή ώρα, και σε έναν πίνακα ~N \times N~ έγραψε, για κάθε δύο κόμβους, τον αριθμό των διαφορετικών χρωμάτων σε ένα μοναδικό απλό μονοπάτι μεταξύ (και συμπεριλαμβανομένου) αυτών των δύο κόμβων Δυστυχώς, θαυμάζοντας όλα αυτά τα χρώματα, ο Nikola ξέχασε εντελώς πώς ήταν το δέντρο και ποια χρώματα ήταν στους κόμβους.
Χρειάζεται λοιπόν τη βοήθειά σας. Από τον πίνακα που έγραψε, προσδιορίστε ένα πιθανό δέντρο και πιθανά χρώματα στους αντίστοιχους κόμβους. Τα χρώματα πρέπει να συμβολίζονται με αριθμούς από {~1, 2, \cdots, N~}. Είναι εγγυημένο ότι ο Nikola δεν έκανε λάθος, με άλλα λόγια θα υπάρχει λύση.

Είσοδος

Η πρώτη γραμμή περιέχει έναν αριθμό υποπροβλήματος (~1~, ~2~ ή ~3~) από την ενότητα Βαθμολογία παρακάτω.
Η δεύτερη γραμμή περιέχει έναν ακέραιο ~N (1 \le N \le 3\,000)~, τον αριθμό των κόμβων στο δέντρο, οι οποίοι συμβολίζονται με ~1, 2, \cdots, N~.
Κάθε μία από τις επόμενες ~N~ γραμμές περιέχει ~N~ ακέραιους αριθμούς, όπου ο ~j~-ος αριθμός στην ~i~-η γραμμή ισούται με τον αριθμό των διαφορετικών χρώματων στη διαδρομή από τον κόμβο ~i~ στον κόμβο ~j~.

Έξοδος

Η πρώτη γραμμή πρέπει να περιέχει ~N~ ακέραιους αριθμούς που χωρίζονται με ένα διάστημα μεταξύ ~1~ και ~N~: τα χρώματα των κόμβων ~1, 2, \cdots,N~.
Κάθε μία από τις επόμενες ~N - 1~ γραμμές πρέπει να περιέχει δύο ακέραιους αριθμούς ~A~, ~B~ που αντιπροσωπεύουν την ακμή (γειτονικοί κόμβοι) στο δέντρο. Η σειρά των ακμών και των κόμβων μέσα σε μια ακμή είναι αυθαίρετη.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	18	Όλοι οι αριθμοί στον πίνακα είναι ίσοι με ~1~ ή ~2~
2	25	Υπάρχει μια λύση όπου το δέντρο είναι άλυσος των κόμβων ~1, 2, \cdots, N~ με αυτή τη σειρά,δηλαδή οι ακμές είναι ~(i,\,i+1)~ για κάθε ~i = 1, \cdots, N-1~.
3	57	Κανένας επιπλέον περιορισμός.

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

input

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

output

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

input

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

output

1 2 3 2
1 2
2 3
3 4

input

1
5
1 2 2 2 2
2 1 1 2 2
2 1 1 2 2
2 2 2 1 2
2 2 2 2 1

output

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