Choosing Chicken-Fight Teams

Chicken fighting is a long-standing tradition in this fictional world. At this camp, a chicken-fighting tournament is being held again. To run the tournament, every student must know who is on the same side and who is not.

Teams are determined from the students' relationships by these rules:

1. A friend of my friend is also my friend.
2. An enemy of my enemy is also my friend.

If two students are friends, they must belong to the same team. Also, everyone in the same team must be friends with each other.

Given the known relationships among the students, write a program that finds the maximum possible number of teams that can be formed.

The first line contains the number of students n. The students are numbered from 1 to n. (2 <= n <= 1000)

The second line contains the number m of known relationships between students. (1 <= m <= 5000)

Each of the next m lines contains one relationship in the form F p q or E p q, separated by spaces. (1 <= p < q <= n)

If the first letter is F, students p and q are friends. If it is E, they are enemies.

The input is guaranteed to have no contradiction. In other words, no two students are both friends and enemies at the same time.

Print the maximum possible number of teams on the first line.

One optimal grouping is to place student 1 alone, students 2, 4, and 6 together, and students 3 and 5 together. This gives the maximum number of teams.