/*
  BOI 2003 competition
  GANGS task solution
  By Matti Nykänen (e-mail: matti.nykanen@cs.helsinki.fi), task proposer

  USAGE: Reads from stdin, prints to stdout, no command line parameters.

  Correctness of the algorithm is argued in a separate document.
*/

/*
  The task parameters:
  MAX_M = maximum number of gangsters. Gangsters are numbered 1,2,3,...
  MAX_N = maximum number of input facts.
*/
#define MAX_M 1000
#define MAX_N 5000

#include <stdio.h>

/*
  The undirected graph with
  * gangsters as nodes
  * friendships as edges
  as an array of adjacency lists.
*/
typedef struct graphnode *NodePtr;
typedef struct graphedge *EdgePtr;
typedef struct graphedge {
  NodePtr this;
  EdgePtr next;
} Edge;
typedef struct graphnode {
  /* The list of nodes adjacent to this node. NULL means empty. */
  EdgePtr adjacent;
  /* Designated enemy. NULL means none. */
  NodePtr foe;
  /* 
     Status of this node:
     0 = still unprocessed by depth-first search.
     1,2,3,... = this node has been assigned to this connected
     component
  */
  int component;
} Node;
Node nodes[MAX_M+1];
/*
  Each bidirectional edge is stored as two unidirectional edges.
  Each E(nemy) fact can add two new edges.
  Hence this allocation.
*/
Edge edges[2*2*MAX_N];
EdgePtr next_free = edges;

/*
  Add an edge from a given node into another.
*/
void add_edge(NodePtr from, NodePtr into)
{
  EdgePtr next_used = next_free++;
  next_used->this   = into;
  next_used->next   = from->adjacent;
  from->adjacent    = next_used;
}
void add_friends(NodePtr node1, NodePtr node2)
{
  add_edge(node1, node2);
  add_edge(node2, node1);
}

void add_foe(NodePtr node1, NodePtr node2)
{
  if(node1->foe == NULL)
    node1->foe = node2;
  else
    add_friends(node1->foe, node2);
}

/*
  Perform depth-first traversal from this node whose component field
  has just been set.
*/
void traverse(NodePtr from)
{
  EdgePtr into;
  for(into=from->adjacent; into != NULL; into=into->next)
    if(into->this->component == 0)
      {
	into->this->component = from->component;
	traverse(into->this);
      }
}


int main(int argc,char argv[])
{
  int M; /* Number of gangsters. */
  int N; /* Number of input facts. */
  int node,fact,gangster1,gangster2,components;
  NodePtr node1,node2;
  char relation;
  /* Node initializer: no adjacent nodes, no foe, not processed. */
  Node empty_node = {NULL,NULL,0};

  /* Open the input and output text files. */
  FILE *input = fopen("GANGS.IN","r");
  FILE *output = fopen("GANGS.OUT","w");

  /* Read the size of this task instance. */
  if(fscanf(input,"%d\n%d\n", &M, &N)!=2)
    return 1;
  
  /*
    Initialize the graph nodes to be empty. Probably redundant, since
    automatic initialization of static vectors is all 0. But there
    _might_ be some machine architecture where NULL!=0 ...
  */
  for(node=1; node<=M; node++)
    nodes[node] = empty_node;
  
  /*
    Read in the facts, and generate the corresponding graph edges.
  */
  for(fact=1; fact<=N; fact++)
    {
      if(fscanf(input,"%c %d %d\n", &relation, &gangster1, &gangster2)!=3)
	return 1;
      /* Convert gangster indices to node pointers. */
      node1 = nodes+gangster1;
      node2 = nodes+gangster2;
      switch(relation){
      case 'F':
	/*
	  Friend fact creates the correspoding undirected edge.
	*/
	add_friends(node1, node2);
	break;
      case 'E':
	/*
	  Enemy fact either introduces a foe or induces an edge.
	*/
	add_foe(node1, node2);
	add_foe(node2, node1);
	break;
      default:
	return 1;
      }
    }

  /*
    Assign the nodes to distinct connected components using
    depth-first traversal.
  */
  components = 0;
  for(node=1; node<=M; node++)
    {
      NodePtr atnode = nodes+node;
      if(atnode->component == 0)
	{
	  atnode->component = ++components;
	  traverse(atnode);
	}
    }
  
  /*
    Verify that no foes have become friends.
  */
  for(node=1; node<=M; node++)
    if((nodes[node].foe != NULL)&&
       (nodes[node].foe->component == nodes[node].component))
      {
	components = 0;
	break;
      }

  /*
    Output the result.
  */
  fprintf(output,"%d\n", components);

  /*
    Exit cleanly.
  */
  fclose(output);
  fclose(input);
  return 0;
}