Lista

Ο Mirko έλαβε ένα δώρο γενεθλίων από τη θεία του στις ΗΠΑ – μια ολοκαίνουργια λίστα με διπλά συνδεδεμένα στοιχεία (ένα παράδειγμα εκ των οποίων φαίνεται στο παρακάτω σχήμα). Η λίστα περιέχει ~N~ κόμβους με αριθμό από ~1~ έως ~N~. Δύο τύποι κινήσεων μπορούν να γίνουν στη λίστα:

Α) Μετακίνηση του κόμβου ~X~ μπροστά από τον κόμβο ~Y~.
Β) Μετακίνση του κόμβου ~X~ πίσω από τον κόμβο ~Y~.

Ένα παράδειγμα λίστας με ~6~ κόμβους.

Η λίστα μετά την κίνηση «~A\;1\;4~».

Η λίστα μετά από μια άλλη κίνηση, «~B\;3\;5~».

Ο Mriko έπαιζε με το νέο του παιχνίδι για ώρες, σημειώνοντας κάθε κίνηση σε ένα χαρτί για να μπορεί να ανακατασκευάσει την αρχική κατάσταση της λίστας (κόμβοι ~1~ έως ~N~ με σειρά από αριστερά προς τα δεξιά).
Όταν αποφάσισε να ανασκευάσει τη λίστα, ο Mirko έμεινε έκπληκτος όταν διαπίστωσε ότι δεν υπήρχε εύκολος τρόπος να αντιστρέψει τις κινήσεις και να επαναφέρει στην αρχική της κατάσταση τη λίστα. Ο Mirko δεν μπορεί να γνωρίζει πού ήταν ο κόμβος ~X~ πριν από καθέ κίνηση, μόνο εκεί που κατέληξε.
Βλέποντας πώς ο Mirko εξακολουθεί να αναρρώνει από το σοκ, γράψτε ένα πρόγραμμα που βρίσκει μια ελάχιστη ακολουθία κινήσεων που επανέφερουν στην αρχική της κατάσταση τη λίστα σύμφωνα με τα αρχεία καταγραφής του Mirko.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους αριθμούς ~N~ και ~K (2 \le N \le 500\,000,\;0 \le M \le 100\,000)~, τον αριθμό των κόμβων και τον αριθμό των κινήσεων που έκανε ο Mirko.
Κάθε μία από τις επόμενες ~M~ σειρές περιέχει μια περιγραφή μιας μεμονωμένης κίνησης που έκανε ο Mirko – το είδος της κίνησης («\(Α\)» ή «\(Β\)») και δύο ακέραιοι ~X~ και ~Y~.

Έξοδος

Εκτυπώστε τον ελάχιστο αριθμό κινήσεων (καλέστε αυτόν τον αριθμό ~K~) στην πρώτη γραμμή.
Κάθε μία από τις επόμενες ~K~ γραμμές πρέπει να περιέχει μια περιγραφή μιας μεμονωμένης κίνησης με την ίδια μορφή όπως στο είσοδο.
Σημείωση: Η ακολουθία δεν χρειάζεται να είναι μοναδική.

Βαθμολογία

Εάν και ο αριθμός ~K~ και η ακολουθία των κινήσεων είναι σωστές, το πρόγραμμά σας θα συγκεντρώσει πλήρεις πόντους στο αρχείο ελέγχου.
Εάν το πρόγραμμά σας εκτυπώνει τον σωστό αριθμό \(Κ\) και δεν εκτυπώνει την ακολουθία κινήσεων ή η ακολουθία των κινήσεων είναι λανθασμένη, θα λάβετε το ~60~% των πόντων για αυτό το αρχείο ελέγχου.

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

input

2 1
A 2 1

output

1
A 1 2

input

4 3
Β 1 2
Α 4 3
Β 1 4

output

2
Α 1 2
Β 4 3

input

6 5
Α 1 4
Β 2 5
Β 4 2
Β 6 3
Α 3 5

output

3
A 4 5
B 6 5
A 2 3