거짓말쟁이와 진실만 말하는 소

한 농부가 소들과 오랜 시간을 보내면서 소들의 언어를 이해하게 되었다. 농부는 자신의 소 $N$마리($2 \le N \le 1000$) 중 일부는 항상 진실만 말하고, 나머지는 항상 거짓말만 한다는 사실을 알아차렸다.

농부는 소들이 한 $M$개의 진술($1 \le M \le 10\,000$)을 받아 적었다. 각 진술은 다음 두 형태 중 하나이다.

• x y T — 소 $x$가 "소 $y$는 항상 진실만 말한다"라고 주장한다.
• x y L — 소 $x$가 "소 $y$는 항상 거짓말만 한다"라고 주장한다.

모든 진술은 서로 다른 두 소에 대한 것이며, 같은 소 쌍이 여러 진술에 등장할 수 있다.

농부는 일부 진술을 잘못 받아 적었을 수도 있다고 의심한다. 따라서 $M$개의 진술 모두와 모순되지 않도록 각 소를 '진실만 말하는 소' 또는 '거짓말쟁이'로 정하는 방법이 존재하지 않을 수도 있다. 목록을 최대한 살리기 위해, 앞에서부터 $A$개의 진술과 모순되지 않는 소들의 배정이 존재하도록 만들 수 있는 가장 큰 $A$의 값을 구하여라.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
• 둘째 줄부터 $M+1$째 줄까지: 각 줄은 x y T 또는 x y L 형태이며, 소 $x$가 소 $y$에 대해 한 진술 하나를 나타낸다 ($1 \le x, y \le N$, $x \ne y$).

• 첫째 줄: $N$마리 소를 '진실만 말하는 소' 또는 '거짓말쟁이'로 배정했을 때 앞에서부터 $A$개의 진술과 모순되지 않게 만들 수 있는 가장 큰 $A$의 값.

예제에서 1번과 3번 진술은 동시에 성립할 수 없지만, 1번과 2번 진술은 동시에 성립할 수 있다. 소 1, 2, 3이 진실만 말하고 소 4가 거짓말쟁이라고 하면 된다.