#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
const int MAXN = 500000;
vector<int> trainGraph[MAXN + 1];
vector<int> busGraph[MAXN + 1];
vector<int> trainComponent(MAXN + 1, -1);
unordered_map<int, unordered_set<int>> componentCities; // Cities in each train component
unordered_map<int, unordered_set<int>> componentNeighbors; // Components reachable via one bus
// Perform BFS to find all cities in the same train component
void bfsTrain(int start, int componentID) {
queue<int> q;
q.push(start);
trainComponent[start] = componentID;
componentCities[componentID].insert(start);
while (!q.empty()) {
int city = q.front();
q.pop();
for (int neighbor : trainGraph[city]) {
if (trainComponent[neighbor] == -1) {
trainComponent[neighbor] = componentID;
componentCities[componentID].insert(neighbor);
q.push(neighbor);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
// Build the graph
for (int i = 0; i < M; ++i) {
int a, b;
char type;
cin >> a >> b >> type;
if (type == 'T') {
trainGraph[a].push_back(b);
trainGraph[b].push_back(a);
} else if (type == 'A') {
busGraph[a].push_back(b);
busGraph[b].push_back(a);
}
}
// Step 1: Find train components
int componentCount = 0;
for (int i = 1; i <= N; ++i) {
if (trainComponent[i] == -1) {
bfsTrain(i, componentCount++);
}
}
// Step 2: Precompute neighbors of each train component via one bus trip
for (int city = 1; city <= N; ++city) {
int currentComponent = trainComponent[city];
for (int neighbor : busGraph[city]) {
int neighborComponent = trainComponent[neighbor];
if (currentComponent != neighborComponent) {
componentNeighbors[currentComponent].insert(neighborComponent);
}
}
}
// Step 3: Calculate the maximum reachable cities for each city
int maxReachable = 0, countMaxCities = 0;
for (int city = 1; city <= N; ++city) {
int currentComponent = trainComponent[city];
// Start with all cities in the current train component
unordered_set<int> reachableCities = componentCities[currentComponent];
// Add cities from other components reachable via a single bus trip
for (int neighborComponent : componentNeighbors[currentComponent]) {
reachableCities.insert(componentCities[neighborComponent].begin(),
componentCities[neighborComponent].end());
}
int reachableCount = reachableCities.size();
if (reachableCount > maxReachable) {
maxReachable = reachableCount;
countMaxCities = 1;
} else if (reachableCount == maxReachable) {
countMaxCities++;
}
}
// Step 4: Output the result
cout << countMaxCities << "\n";
return 0;
}
