Monthly Railway Pass

Time limit2sMemory limit1024 MB

Summary

A graph has train and bus edges. Count cities from which every other city is reachable using any number of train edges and at most one bus edge.

Level: Medium6 of 10
Topics: Graph, DFS, Union-find
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Constraints

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

Examples2

Example 1
Input
```
5 5
3 1 A
3 5 A
4 5 T
2 3 T
2 1 A
```
Expected output
```
2
```

Example 2

Input

Expected output