Laiko ribojimas: 1s
Atminties ribojimas: 64MB
Duomenų failas: lmio_2018_3e2_menesinis_bilietas_jau.in
Rezultatų failas: lmio_2018_3e2_menesinis_bilietas_jau.out
Mėnesinis bilietas
Užduotis
Bitlandijoje yra 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 ir transporto linijų skaičius . Miestai yra žymimi skaičiais nuo 1 iki imtinai.
Tolimesnėse eilučių pateikiama po 2 skaičius ir bei ženklą . -toji transporto linija jungia miestus ir , o ženklas nurodo šios linijos transporto priemonės tipą. Jei yra T, tai -tąja linija kursuoja traukiniai, jei 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. |