#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct miestas{
bool aplankytas;
vector<int> autikai; // kokius miestus gali pasiekt autiku
vector<int> traukiniai; // kokius miestus gali pasiekt traukiniu
int grupe; // kokiam jungumo komponentui priklauso
miestas() : aplankytas(false), grupe(-1) {}
};
vector<miestas> miestai;
// visus miestus, kurie pasiekiami is i-tojo miesto traukiniu priskiriam gr grupe
void priskirk_grupe(int i, int gr) // realiai dfs + spalvinimo algoritmas is https://inf-knyga.nmakademija.lt/lt/latest/07_grafų_pagrindai.html#paieska-gilyn
{
miestai[i].grupe = gr;
for(int kaimynas : miestai[i].traukiniai)
{
if(miestai[kaimynas].grupe != -1) // jeigu kaimynas priklauso kitam jungumo komponentui
continue;
priskirk_grupe(kaimynas, gr); // einam lankyt kaimyno kaimynu
}
}
int rask_gretimas_komp(int i, vector<bool>& ak)
{
miestai[i].aplankytas = true;
int dydis = 1;
// aplankom visas i-tojo miesto kaimynu komponentes vienu autiku
for(int idx : miestai[i].autikai)
{
ak[miestai[idx].grupe] = true;
}
for(int idx : miestai[i].traukiniai)
{
if(miestai[idx].aplankytas)
continue;
dydis += rask_gretimas_komp(idx, ak);
}
return dydis;
}
// jei is i-tojo miesto galim pasiekt
int rask_bendros_komp_miestu_sk(int i, int grsk)
{
vector<bool> ak(grsk, false); // aplankyti komponentai
ak[miestai[i].grupe] = true; // nes save galim aplankyt
int ans = rask_gretimas_komp(i, ak);
for(int i = 0; i < grsk; i++)
{
if(ak[i] == false) // jeigu yra neaplankytu komponentu
return 0; // tai mes is miesto i negalim pasiekt visu kitu miestu
}
return ans;
}
int main()
{
int N, M; // N - miestai, M - transp. linijos
cin >> N >> M;
miestai.resize(N); // bus tik N miestu
for(int i = 0; i < M; i++)
{
int a, b;
char t;
cin >> a >> b >> t;
if(t == 'T')
{
miestai[a-1].traukiniai.pb(b-1); // sitose eilutese is indekso ir pb args atemam 1, nes miestai sunumeruoti 1 -> N, o vektoriaus indeksai 0 -> N-1
miestai[b-1].traukiniai.pb(a-1);
}
else if(t == 'A')
{
miestai[a-1].autikai.pb(b-1);
miestai[b-1].autikai.pb(a-1);
}
}
// suskirstom miestus i jungumo komponentu grupes
int grupe = 0;
for(int i = 0; i < N; i++)
{
if(miestai[i].grupe == -1)
{
priskirk_grupe(i, grupe);
grupe++;
}
}
//
int ans = 0;
for(int i = 0; i < N; i++)
{
if(!miestai[i].aplankytas)
ans += rask_bendros_komp_miestu_sk(i, grupe);
}
cout << ans;
return 0;
}
