Baltic Olympiad in Informatics, April 23-27, 2003, Tartu, Estonia

The Gangs

Chicago in the 1920s: a battlefield of gangsters.

If two gangsters have ever met each other, then they have become either true friends or mortal enemies. The gangsters live --- and die --- by the following code of ethics:

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

Two gangsters are in the same gang if and only if they are friends.

Poor you are employed by the Chicago Police Department. You must calculate the maximal possible number of different gangs in Chicago based on what the Department knows about the relations between the individual gangsters.

Input data

The first line of the input file GANGS.IN gives the number N (2 ≤ N ≤ 1 000) of known gangsters. The gangsters are numbered from 1 to N. The second line gives the number M (1 ≤ M ≤ 5 000) of known facts about these gangsters.

The following M lines list the facts, each fact on its own line. Each fact is of the form F p q or E p q, where 1 ≤ p < q ≤ N are the two gangsters in question. (Each of the three components is separated by a space.) If the first letter is F, the line says that p and q are known friends. If it is E, then they are known enemies.

It can be assumed that the input is consistent --- two gangsters cannot be both friends and enemies of each other.

Output data

The first and only line of the output file GANGS.OUT must contain the maximal possible number of gangs.

Sample

GANGS.IN GANGS.OUT
6
4
E 1 4
F 3 5
F 4 6
E 1 2
 3

Remark

The 3 gangs in the example above are {1}, {2, 4, 6}, and {3, 5}.