시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 9 4 4 44.444%

문제

상근이는 친구들 중에 거짓말쟁이가 몇 명이나 있는지 알아내려고 한다. 상근이의 친구는 총 N명이며, 항상 거짓말만 하는 친구와 항상 진실만을 이야기하는 친구로 나누어 진다. (2 ≤ N ≤ 1000) 

상근이는 친구들에게 총 M번의 질문을 했다. (1 ≤ M ≤ 10,000) 질문은 x에게 "y가 거짓말쟁이이니?"와 같은 형식이다. x가 y는 거짓말쟁이라고 말했다면 상근이는 종이에 "x y L"라고 적을 것이고, 아니라면 "x y T"라고 적을 것이다.

이러한 질문은 여러 친구에게 물어봤으며, 같은 친구에게 같은 질문을 물어봤을 수도 있다. 하지만, 자기 자신이 거짓말쟁이라고 물어보는 질문은 하지 않는다.

안타깝게도, 상근이는 종이에 질문의 일부를 잘못 쓴 것 같다는 생각이 들었다. 따라서, 종이에 적힌 질문과 대답만으로 누가 거짓말쟁이이고 아닌지를 알아내지 못 할 수도 있다.

상근이가 적어 놓은 질문과 대답 중 처음 A개만 가지고 누가 거짓말쟁이이고 아닌지 알아낼 수 있는 알아내는 프로그램을 작성하시오. 만약 알아낼 수 있다면, A의 최대값을 출력한다.

입력

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 M개 줄에는 상근이의 질문에 대한 대답 정보이며, "x y L" 또는 "x y T" 형태이다.

출력

첫째 줄에 최대 A값을 출력한다.

예제 입력

4 3
1 4 L
2 3 T
4 1 T

예제 출력

2

힌트