Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2018_3e2_menesinis_bilietas_jau.in

Rezultatų failas: lmio_2018_3e2_menesinis_bilietas_jau.out

Jei norite pateikti savo sprendimą - prisijunkite.

Mėnesinis bilietas

Užduotis

Bitlandijoje yra N miestų ir kai kurias jų poras jungia traukinių arba autobusų linijos. Bet kuria linija galima važiuoti abejomis kryptimis. Marijonas ruošiasi mėnesio trukmės atostogoms Bitlandijoje. Jis žada daugiausiai keliauti traukiniais, todėl nusipirko mėnesinį bilietą, kuris leidžia traukiniais keliauti neribotai. Šis bilietas negalioja kelionėms autobusais.

Marijonas ketina apsistoti viename mieste, bet dar nežino, kuriame. Marijonas nori apsistoti tokiame mieste, iš kurio galėtų pigiai nuvažiuoti į bet kurį kitą, nes norės iš miesto, kuriame apsistojo, važinėti į kitus miestus.

Iš vieno miesto į kitą Marijonas gali nuvažiuoti pigiai, jei tarp šių miestų yra toks maršrutas, kuriuo jis važiuotų neribotą kiekį traukiniais, ir ne daugiau nei vieną kartą autobusu.

Suskaičiuokite, kiek Bitlandijoje yra miestų, kuriuose Marijonas gali apsistoti.

Pradiniai duomenys

Pirmoje eilutėje pateikiami du skaičiai: miestų skaičius N ir transporto linijų skaičius M. Miestai yra žymimi skaičiais nuo 1 iki N imtinai.

Tolimesnėse M eilučių pateikiama po 2 skaičius a_i ir b_i bei ženklą T_i. i-toji transporto linija jungia miestus a_i ir b_i, o ženklas T_i nurodo šios linijos transporto priemonės tipą. Jei T_i yra T, tai i-tąja linija kursuoja traukiniai, jei T_i yra A, šia transporto linija važiuoja autobusai.

Rezultatai

Išveskite vieną sveikąjį skaičių – keliuose miestuose Marijonas gali apsistoti.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
5 5
3 1 A
3 5 A
4 5 T
2 3 T
2 1 A
 
2
 
Marijonas gali apsistoti antrame ir trečiame mieste.
< insert image here >
Traukinių maršrutai pažymėti ištisine linija, o autobusų linijos - punktyru.
 
7 8
7 5 A
3 7 A
3 1 A
3 4 T
3 5 A
7 1 A
5 6 T
2 7 T
 
4
 
Pigiai nuvažiuoti į visus miestus galima iš miestų 2, 3, 4 ir 7.

Ribojimai

1\\leqN\\leq20000

1\\leqM\\leq500000