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

#3816
다국어

거짓말쟁이 1초 128MB

문제

권수쌤은 오랜 기간 수업을 하면서 학생들의 언어를 이해하기 시작했다. 더 나아가, 그는 N명의 학생들 중 일부는 항상 진실을 말하고, 다른 일부는 항상 거짓말을 한다는 것을 알아차렸다.

권수쌤은 M개의 진술을 주의 깊게 들었다.

  • "x y T" 형태의 진술은 "학생 x가 학생 y는 항상 진실을 말한다고 주장한다"는 의미이거나,

  • "x y L" 형태의 진술은 "학생 x가 학생 y는 항상 거짓말을 한다고 주장한다"는 의미이다.

  • 각 진술은 서로 다른 두 학생을 포함하고, 동일한 학생이 여러 번 등장할 수 있다.

불행히도, 권수쌤은 자신의 목록에 잘못 기록된 항목이 있을 수 있다고 생각하여, 모든 M개의 진술을 일관되게 진실을 말하는 학생과 거짓말을 하는 학생으로 지정하는 유효한 방법이 존재하지 않을 수 있다고 판단했다. 권수쌤이 자신의 목록에서 가능한 한 많은 진술을 살릴 수 있도록 돕기 위해, "진실을 말하는 학생" 또는 "거짓말을 하는 학생"으로 각 학생을 지정하는 방식이 첫 번째 A개의 진술과 일관되도록 할 수 있는 A의 최대 값을 계산하.


입력

첫 줄에 두 정수 N ,M이 주어진다. (2\le N\le 1,000; 1 \le M\le 10,000)

두 번째 줄부터 M+1번째 줄까지 "x y L" 혹은 "x y T"의 형태의 진술이 주어지며, 이는 학생 x가 학생 y에 대해 진술하는 내용이다.


출력

첫 줄에 첫 A개의 진술이 항상 진실한 학생과 진술이 항상 거짓인 학생에 대해 일관되게 지정할 수 있게 하는 A의 최댓값을 출력한다.


예제1

입력
4 3
1 4 L
2 3 T
4 1 T
출력
2

진술 1과 3은 동시에 만족할 수 없지만, 진술 1과 2는 만족할 수 있다. 이 경우 소 1부터 3까지는 진실을 말하고 소 4는 거짓말을 한다고 지정할 수 있다.


태그

출처

USACO 2013 January Bronze

역링크 공식 문제집만