Travelling Salesperson

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

Αν θέλαμε να ταξιδέψουμε σε ένα μπλε δρόμο ξανά αφού έχουμε επισκεφθεί την κορυφή ~3~ για δεύτερη φορά, θα χρειαζόμασταν άλλο ένα εισητήριο, για ένα σύνολο δύο εισητηρίων:

Είστε ένας περιπλανώμενος πωλητής που επισκέπτεται την πόλη του ΚοκκινοΜπλε, και επιθυμείτενα επισκεφθείτε κάθε κτήριο τουλάχιστον μία φορά, ενώ ελαχιστοποιείτε τις επαναλαμβανόμενες επισκέψεις στα ίδια κτήρια. Δεν έχετε αποφασίσει ακόμα από ποιο κτήριο θα ξεκινήσετε τη διαδρομή σας, οπότε θα θέλατε να σχεδιάσετε όλες τις πιθανές διαδρομές. Επιπλέον, έχετε πρόσβαση σε ένα μόνο εισητήριο. Για κάθε κτήριο, θα θέλατε να βρείτε μια διαδρομή ελάχιστου μήκουςπου ξεκινά από αυτό το κτήριο, επισκέπτεται όλα τα κτήρια τουλάχιστον μία φορά και χρησιμοποιεί το πολύ ένα εισητήριο.

Είσοδος

Η πρώτη γραμμή θα περιέχει έναν ακέραιο ~N~ (~2~ ~\le~ ~N~ ~\le~ ~2\,000~), τον αριθμό των κτηρίων στη πόλη ΚοκκινοΜπλε.

Οι γραμμές ~2~ έως ~N~ περιέχουν η καθεμία μία συμβολοσειρά, με τη γραμμή ~i~ να περιέχει τη συμβολοσειρά ~C_i~. που αντιπροσωπεύει τα χρώματα των δρόμων που συνδέονται με το κτήριο ~i~. Η συμβολοσειρά ~C_i~ = ~C_{i,1}~~C_{i,2}~ ... ~C_{i,i-1}~ έχει μήκος ~i-1~ και αποτελείται μόνο από τους χαρακτήρες ~R~ και ~B~. Αν το ~C_{i,j}~ είναι ~R~, τότε ο δρόμος μεταξύ των κτηρίων ~i~ και ~j~ είναι κόκκινος. Αλλιώς, είναι μπλε.

Έξοδος

Εκτυπώστε ~2N~ γραμμές. Οι γραμμές ~2i~ - ~1~ για ~1~ ~\le~ ~i~ ~\le~ ~N~ θα πρέπει να περιέχουν έναν ακέραιο ~M_i~, που αντιπροσωπεύει το μήκος του "ταξιδιωτικού σχεδίου" που ξεκινά από το κτήριο ~i~. Οι γραμμές ~2i~ για ~1~ ~\le~ ~i~ ~\le~ ~N~ θα πρέπει η καθεμία να περιέχει ~M_i~ ακέραιους χωρισμένους με κενά, που περιγράφουν την σειρά με την οποία θα επισκεφθείτε τα κτήρια, ξεκινώντας από το κτήριο ~i~.

Βαθμολογία

Για κάθε ένα από τα "ταξιδιωτικά σχέδιά" σας, υπολογίζεται μια βαθμολογία. Έστω ~K_i~ το μήκος της βέλτιστης διαδρομής που ξεκινά από κάθε κτήριο και ~M_i~ το μήκος της διαδρομής σας. Αν το ~M_i~ είναι μεγαλύτερο από το ~2K_i~, τότε η βαθμολογία σας θα είναι ~0~ και θα λάβετε μια ετυμηγορία Wrong Answer. Αν το ~M_i~ είναι ίσο με το ~K_i~, τότε η βαθμολογία σας θα είναι ~25~. Αλλιώς η βαθμολογία σας θα είναι ⌊~8~ + ~8~ ~\cdot~ ~(2K_i - M_i) / (K_i-1)~⌋. Η βαθμολογία σας για τo παράδειγμα είναι η ελάχιστη βαθμολογία για κάθε "ταξιδιωτικό σχέδιο".

Αν κάποιο από τα σχέδιά σας είναι άκυρο, η βαθμολογία σας θα είναι ~0~ και θα λάβετε μια ετυμηγορία Wrong Answer.

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

Παράδειγμα

input

4
R
RR
BRB

possible output

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

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

Η πόλη ΚοκκινοΜπλε είναι όπως φαίνεται παρακάτω:

Η διαδρομή που ξεκινά από το κτήριο ~3~ έχει ένα βέλτιστο μήκος ~4~ επισκέπτοντας τα κτήρια με τη σειρά ~3~,~2~,~1~,~4~. Η διαδρομή της λύσης έχει μήκος ~5~, που σημαίνει ότι η βαθμολογία είναι ⌊~8~ + ~8~ ~\cdot~ (~2~ ~\cdot~ ~4~ - ~5~) / (~4~ - ~1~)⌋ = ~16~.