시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 1908 | 871 | 656 | 45.651% |
닭싸움은 월드의 전통이다. 이번 캠프에서도 어김없이 닭싸움 대회가 열렸다. 그런데, 닭싸움을 하기 위해서는 반드시 누가 우리 편이고, 누가 우리 편이 아닌지를 알아야 할 것이다. 닭싸움의 팀을 정하는 원칙은, 평소 학생들의 인간관계에 따라 다음과 같이 정리할 수 있다.
이 때 두 학생이 친구이면 같은 팀에 속해있어야 하며, 같은 팀에 속해 있는 사람들끼리는 전부 친구여야 한다.
학생들의 인간관계가 주어지면, 닭싸움을 위한 팀 정하기를 할 때, 최대 얼마나 많은 팀이 만들어질 수 있는지 알아내는 프로그램을 작성하시오.
첫째 줄에 학생의 수 n이 주어진다. 각 학생들은 1부터 n까지 번호가 매겨져 있다. (2 ≤ n ≤ 1000)
둘째 줄에 학생 간의 인간관계 중 알려진 것의 개수 m이 주어진다. (1 ≤ m ≤ 5000)
다음 m개의 줄에는 한 줄에 한 개씩, 학생 간의 인간관계가 F p q 혹은 E p q의 형태로 공백으로 구분되어 주어진다. (1 ≤ p < q ≤ n)
첫 번째 글자가 F인 경우에는 p와 q가 친구인 것이고, E인 경우는 p와 q가 원수인 경우이다.
입력은 모순이 없음이 보장된다. 즉, 두 학생이 동시에 친구이면서 원수인 경우는 없다.
첫째 줄에, 가능한 최대 팀 개수를 출력한다.
6 4 E 1 4 F 3 5 F 4 6 E 1 2
3
1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다.