닭싸움 팀 정하기

닭싸움은 이 세계의 오랜 전통이다. 이번 캠프에서도 닭싸움 대회가 열린다. 대회를 진행하려면 각 학생이 누구와 같은 편이고, 누구와 같은 편이 아닌지 알아야 한다.

팀은 학생들의 평소 인간관계를 바탕으로 다음 규칙에 따라 정한다.

1. 내 친구의 친구는 내 친구이다.
2. 내 원수의 원수도 내 친구이다.

두 학생이 친구라면 반드시 같은 팀에 속해야 한다. 또한 같은 팀에 속한 사람들은 서로 모두 친구여야 한다.

학생들의 알려진 인간관계가 주어질 때, 닭싸움을 위한 팀을 최대 몇 개까지 만들 수 있는지 구하는 프로그램을 작성하시오.

첫째 줄에 학생의 수 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는 원수이다.

입력에는 모순이 없음이 보장된다. 즉, 같은 두 학생이 동시에 친구이면서 원수인 경우는 없다.

첫째 줄에 만들 수 있는 최대 팀의 수를 출력한다.

한 가지 최적의 구성은 1번 학생을 혼자 두고, 2번, 4번, 6번 학생을 한 팀으로, 3번, 5번 학생을 한 팀으로 묶는 것이다. 이때 팀의 개수가 최대가 된다.