레이팅 미적용소들과 오랜 시간을 보낸 농부 존(Farmer John)은 소들의 언어를 이해하기 시작했다. 게다가 존은 N마리 (2 <= N <= 1000)의 소들 중 일부는 항상 진실만 말하고, 다른 일부는 항상 거짓말만 한다는 것을 알아챘다.
FJ는 소들의 M개 (1 <= M <= 10,000)의 발언을 주의 깊게 듣는다. 각 발언은 "소 x가 소 y는 항상 진실을 말한다고 주장한다"는 뜻의 "x y T" 또는 "소 x가 소 y는 항상 거짓말을 한다고 주장한다"는 뜻의 "x y L" 형태이다. 각 발언은 서로 다른 두 소에 관한 것이며, 같은 소 쌍이 여러 발언에 나타날 수 있다.
안타깝게도 FJ는 목록의 일부 항목을 잘못 받아 적었을 수도 있다고 생각한다. 따라서 M개의 발언 전체와 일치하도록 각 소를 진실만 말하는 소 또는 거짓말쟁이로 지정하는 유효한 방법이 없을 수도 있다. FJ가 목록을 최대한 살릴 수 있도록, FJ의 목록의 처음 A개의 항목과 일치하도록 각 소를 진실만 말하는 소 또는 거짓말쟁이로 지정하는 유효한 방법이 존재하는 A의 최댓값을 계산하시오.
첫째 줄: 공백으로 구분된 두 정수 N과 M.
둘째 줄부터 1+M번째 줄까지: 각 줄은 소 x가 소 y에 대해 한 발언을 설명하는 "x y L" 또는 "x y T" 형태이다.
FJ의 목록의 처음 A개 항목이 N마리의 소에 대한 "진실만 말하는 소" 또는 "거짓말쟁이" 지정과 일치할 수 있는 A의 최댓값.
truth.in · 출력을 쓸 파일 truth.out4 3
1 4 L
2 3 T
4 1 T2Output details: Statements 1 and 3 cannot both be satisfied, but statements 1 and 2 can be (cows 1..3 truth, cow 4 liar).
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > January > Bronze