Monthly Railway Pass

There are $N$ cities in Bitlandia. Some pairs of cities are connected by a train line or a bus line, and every connection is bidirectional.

Marijonas is planning a month-long vacation in Bitlandia. He wants to use trains as much as possible, so he bought a monthly railway pass that lets him ride trains without limit for a month. The pass does not cover bus fares, however.

Marijonas will stay in exactly one city, but he has not decided which one yet. Since he plans to visit many cities during his stay, he wants to choose a city from which he can travel cheaply to every other city.

For Marijonas, traveling from one city to another is cheap if there is a route that uses any number of trains and at most one bus.

Count the number of cities Marijonas could stay in — that is, the cities from which he can travel cheaply to all other cities.

The first line contains two integers: the number of cities $N$ and the number of connections $M$. Cities are numbered from $1$ to $N$.

Each of the next $M$ lines contains two integers $a_i$ and $b_i$ and a character $T_i$. The $i$-th connection joins cities $a_i$ and $b_i$. The character $T_i$ gives the type of transport: if $T_i$ is T the connection is a train line, and if $T_i$ is A it is a bus line.

Print a single integer — the number of cities Marijonas could stay in.

• $1 \le N \le 500\,000$
• $0 \le M \le 500\,000$