Description

There are $n$ people, and between any two people there are two kinds of relations: friend and enemy. We know:

• A person's friend's friend is also a friend.
• A person's enemy's enemy is a friend.

We want to form groups. Two people are in the same group if and only if they are friends. Find the maximum possible number of groups among these people.

Input Format

The first line contains an integer $n$, the number of people.

The second line contains an integer $m$, meaning that $m$ relations follow.

Each of the next $m$ lines contains a character $opt$ and two integers $p, q$, representing the type of relation (friend or enemy), the first person, and the second person among the two who have a relation. The character $opt$ has two possibilities:

• If $opt$ is F, then $p$ and $q$ are friends.
• If $opt$ is E, then $p$ and $q$ are enemies.

Output Format

Output a single integer on one line: the maximum number of groups.

6
4
E 1 4
F 3 5
F 4 6
E 1 2

3

Hint

For $100\%$ of the testdata, $2 \le n \le 1000$, $1 \le m \le 5000$, $1 \le p, q \le n$.

Translated by ChatGPT 5