7259번 - Monthly railway pass 서브태스크다국어

There are N cities in Bitlandia. Some cities are connected by train or bus, and connections work both ways. Marijonas is preparing for a month-long vacation in Bitlandia. He wants to use trains as much as possible, so he bought a monthly railway ticket. This ticket allows Marijonas unlimited train travel for a month, but it does not cover the cost of bus trips.

Marijonas wants to stay in one city - but is not yet sure in which one. Marijonas would like to stay in a city which allows for a cheap travel to all other cities, because he intends to travel to some of them while staying in the chosen city.

For Marijonas, going from one city to another is cheap if there is a route on which he travels on an unlimited number of trains and at most one bus.

Calculate the number of Bitlandia cities Marijonas could stay in.

Two numbers are given in the first line: the number of cities N, and the number of connections between two cities M. Cities are labeled by 1 up to N, inclusive.

Each of the next M lines consist of two numbers, a_i and b_i, and a character T_i. The i-th connection connects cities a_i and b_i, while the character T_i indicates the transportation type of the connection: if T_i is T, then the i-th connection is by train, and if T_i is A, it is by bus.

Output a single integer – the number of cities Marijonas could stay in.

• 1 ≤ N ≤ 500 000
• 0 ≤ M ≤ 500 000