Liars and Truth Tellers

Μετά από τόσο χρόνο που έχει περάσει με τις αγελάδες του, ο Γιάννης ο αγρότης άρχισε να καταλαβαίνει τη γλώσσα τους. Ακόμη, παρατηρεί ότι μεταξύ των ~N~ αγελάδων του ~(2 \le N \le 1000)~, κάποιες λένε πάντα την αλήθεια ενώ άλλες πάντα ψεύδονται.

Ο Γιάννης ακούει προσεκτικά ~M~ δηλώσεις ~(1 \le M \le 10.000)~ των αγελάδων του, κάθε μια της μορφής "~x~ ~y~ ~T~", που σημαίνει ότι "η αγελάδα ~x~ υποστηρίζει ότι η αγελάδα ~y~ λέει πάντα την αλήθεια", ή "~x~ ~y~ ~L~", που σημαίνει ότι "η αγελάδα ~x~ υποστηρίζει ότι η αγελάδα ~y~ λέει πάντα ψέματα". Κάθε δήλωση αφορά ένα ζευγάρι διαφορετικών αγελάδων, και το ίδιο ζευγάρι αγελάδων μπορεί να εμφανιστεί σε πολλές δηλώσεις.

Δυστυχώς, ο Γιάννης πιστεύει ότι ίσως έχει κάνει κάποιες εσφαλμένες καταχωρήσεις στη λίστα του, οπότε ενδέχεται να μην υπάρχει ένας έγκυρος τρόπος να διακρίνει κάθε αγελάδα ως αξιόπιστη (λέει πάντα αλήθεια) ή αναξιόπιστη (λέει πάντα ψέματα), που να είναι συνεπής με όλες τις ~M~ δηλώσεις στη λίστα του. Για να βοηθήσετε τον Γιάννη να σώσει όσο το δυνατόν περισσότερες από τις καταχωρήσεις του, παρακαλούμε να υπολογίσετε τη μεγαλύτερη τιμή του ~A~, ώστε να υπάρχει ένας έγκυρος τρόπος να διακρίνουμε κάθε αγελάδα σε αξιόπιστη ή αναξιόπιστη, που να είναι συνεπής με τις πρώτες ~A~ καταχωρήσεις στη λίστα του.

Είσοδος

• Γραμμή ~1~: Δύο ακέραιοι αριθμοί χωρισμένοι με ένα κενό: ~N~ και ~M~.

• Γραμμές ~2..1+M~: Κάθε γραμμή είναι της μορφής "~x~ ~y~ ~T~" ή "~x~ ~y~ ~L~" και περιγράφει μια δήλωση που έκανε μια αγελάδα ~x~ για μια αγελάδα ~y~.

Έξοδος

• Γραμμή ~1~: Τη μέγιστη τιμή του ~A~ ώστε οι πρώτες ~A~ καταχωρήσεις στη λίστα του Γιάννη να είναι συμβατές με κάποια ανάθεση "αξιόπιστη" (truth teller) ή "αναξιόπιστη" (liar) στις ~N~ αγελάδες.

Παράδειγμα

input

4 3
1 4 L
2 3 T
4 1 T

output

2

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

Υπάρχουν ~4~ αγελάδες και ~3~ δηλώσεις. Η αγελάδα ~1~ λέει ότι η αγελάδα ~4~ ψεύδεται, η αγελάδα ~2~ λέει ότι η αγελάδα ~3~ λέει την αλήθεια, και η αγελάδα ~4~ λέει ότι η αγελάδα ~1~ λέει την αλήθεια. Οι δηλώσεις ~1~ και ~3~ δεν μπορούν να ικανοποιηθούν ταυτόχρονα, αλλά οι δηλώσεις ~1~ και ~2~ μπορούν, αν πούμε πως οι αγελάδες ~1~ έως ~3~ λένε την αλήθεια και η αγελάδα ~4~ ψεύδεται.