페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2534

The Gangs 1s - MB

문제

1920년대 시카고는 갱스터의 전쟁터였다.

이 갱들이 한번이라도 만난 적이 있다면, 그들은 진정한 친구 또는 적 중 하나가 되었습니다.

갱들이 살고 죽는 데는 다음의 윤리에 의해 결정되었다.

  1. 내 친구의 친구도 내 친구이다.

  2. 내 적의 적은 내 친구이다.

두 명의 갱스터가 친구인 경우는 같은 조직이다.

당신은 시카고 경찰서에 새로 파견을 나온 형사이다.

당신은 각 갱스터간의 관계를 가지고 시카고에서 활동 중인 조직의 수를 알아내려고 한다.


입력

입력의 첫줄에는 갱스터들의 수 N(2≤N≤1,000)과 알고 있는 관계의 개수 M(1≤M≤5,000)이 입력된다.

그 다음 줄부터 M줄에 걸쳐 각 줄마다 ‘E’또는 ‘F’와 P, Q가 들어온다.

‘E’는 적을 ‘F’는 친구사이를 나타내고, ‘P’, ‘Q’는 두 갱스터의 번호이다(1≤P〈Q≤N).


출력

출력은 한 줄에 출력하는데 최대로 가능한 조직의 수를 출력한다.


예제 

6 4

E 1 4

F 3 5

F 4 6

E 1 2
3



출처

BOI 2003

로그인해야 코드를 작성할 수 있어요.