시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 175 49 34 25.758%

문제

닭싸움은 월드의 전통이다. 이번 캠프에서도 어김없이 닭싸움 대회가 열렸다. 그런데, 닭싸움을 하기 위해서는 반드시 누가 우리 편이고, 누가 우리 편이 아닌지를 알아야 할 것이다. 닭싸움의 팀을 정하는 원칙은, 평소 학생들의 인간관계에 따라 다음과 같이 정리할 수 있다.

  1. 내 친구는 우리 편이다.
  2. 내 친구의 친구는 우리 편이다.
  3. 내 원수는 우리 편이 아니다.
  4. 내 원수의 원수는 우리 편이다.

학생들의 인간관계가 주어지면, 닭싸움을 위한 팀 정하기를 할 때, 최대 얼마나 많은 팀이 만들어질 수 있는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 학생의 수 n이 주어지고, 둘째 줄에 학생 간의 인간관계 중 알려진 것의 개수 m이 주어진다. (2<=n<=1000, 1<=m<=5000) 셋째 줄부터는 한 줄에 한 개씩 학생 간의 인간관계가 주어진다. 맨 먼저 이 관계가 친구 관계인지, 원수 관계인지를 나타내는 알파벳 대문자가 주어진다. F인 경우에는 친구인 것이고, E인 경우는 원수인 경우이다. 그 다음 두 학생의 번호가 주어진다.

출력

첫째 줄에, 가능한 최대 팀 개수를 출력한다.

예제 입력

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

예제 출력

3

힌트

1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다.

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2003 4번

  • 문제를 번역한 사람: author5
  • 문제의 오타를 찾은 사람: jugol