#include <bits/stdc++.h>
using namespace std;
#define MAX_CITIES 500001 // Maximum number of cities
vector<int> busGraph[MAX_CITIES]; // Adjacency list for bus connections
vector<int> trainGraph[MAX_CITIES]; // Adjacency list for train connections
set<int> componentNeighbors[MAX_CITIES]; // Neighboring components connected via a bus
int trainComponent[MAX_CITIES]; // Train component ID for each city
int componentSize[MAX_CITIES]; // Size of each train component
// Depth-First Search to assign train component IDs
void dfsTrain(int city, int componentID) {
trainComponent[city] = componentID; // Assign current city to the current component
++componentSize[componentID]; // Increment the size of the current component
// Visit all cities directly connected by train
for (int neighbor : trainGraph[city]) {
if (trainComponent[neighbor] == 0) { // If neighbor is unvisited
dfsTrain(neighbor, componentID);
}
}
}
int main() {
int numCities, numConnections; // Number of cities and connections
cin >> numCities >> numConnections;
// Read the graph
for (int i = 0; i < numConnections; ++i) {
int cityA, cityB;
char connectionType;
cin >> cityA >> cityB >> connectionType;
--cityA, --cityB; // Convert to 0-based indexing
if (connectionType == 'T') {
// Train connection
trainGraph[cityA].push_back(cityB);
trainGraph[cityB].push_back(cityA);
} else {
// Bus connection
busGraph[cityA].push_back(cityB);
busGraph[cityB].push_back(cityA);
}
}
// Step 1: Find train-connected components using DFS
int componentCount = 1; // Component ID counter (1-based indexing)
for (int i = 0; i < numCities; ++i) {
if (trainComponent[i] == 0) { // If city is not yet assigned to a component
dfsTrain(i, componentCount++);
}
}
// Step 2: Find neighboring components connected by buses
for (int city = 0; city < numCities; ++city) {
for (int neighbor : busGraph[city]) {
// If the bus connects two different train components
if (trainComponent[city] != trainComponent[neighbor]) {
int componentA = trainComponent[city];
int componentB = trainComponent[neighbor];
componentNeighbors[componentA].insert(componentB);
componentNeighbors[componentB].insert(componentA);
}
}
}
// Step 3: Count valid components
int result = 0; // Total number of valid cities
for (int componentID = 1; componentID < componentCount; ++componentID) {
// Check if the component can reach all other components except itself
if (componentNeighbors[componentID].size() == componentCount - 2) {
result += componentSize[componentID]; // Add the size of the valid component
}
}
// Step 4: Output the result
cout << result << '\n';
return 0;
}
