진실을 말하는 돌고래와 거짓말하는 돌고래

돌고래 사육사인 은영은 돌고래와 많은 시간을 보내면서, 그들의 언어를 이해하기 시작했습니다. 그녀는 N마리의 돌고래들(2 <= N <= 1000) 가운데 일부는 항상 진실을 말하고 다른 일부는 항상 거짓말을 한다는 것을 알게 되었습니다.

은영은 돌고래들로부터 M개의 진술(1 <= M <= 10,000)을 주의 깊게 듣습니다. 각 진술의 형태는 "x y T", 즉, "돌고래 x는 돌고래 y가 항상 진실을 말한다고 주장한다" 또는 "x y L", "돌고래 x는 돌고래 y가 항상 거짓말을 한다고 주장한다"입니다. 각 진술은 다른 두 마리의 돌고래를 포함하며, 동일한 돌고래의 쌍이 여러 서술에서 나타날 수 있습니다.

안타깝게도, 은영은 자신이 들은 진술의 목록에서 일부 항목을 잘못 적은 것 같다고 생각합니다. 따라서 그녀의 목록에 있는 모든 M개의 진술에 대해 각 돌고래를 진실을 말하는 돌고래라고 하거나 거짓말을 하는 돌고래라고 확신할 순 없습니다. 

은영의 진술 목록에서 가능한 많은 부분을 활용하기 위해, 목록의 첫번째 A 항목과 일치하는 방식으로 각 돌고래를 진실을 말하는 돌고래 또는 거짓말하는 돌고래로 배정하는 유효한 방법이 있는 A의 최대값을 계산해 주세요.

• 첫 번째 줄: $N$과 $M$이 공백으로 구분되어 있습니다.
• 두 번째 줄~$1+M$ 번째 줄 : 각 줄은 "x y L" 또는 "x y T" 형태로, 돌고래 $x$가 돌고래 $y$에 대해 한 발언을 나타냅니다.

• 첫 번째 줄: A의 최대 값을 출력하여, 은영의 리스트의 첫 A 항목을 N마리의 돌고래에게 "진실을 말하는 돌고래" 또는 "거짓말하는 돌고래"를 배정하는 일관된 방법이 있다는 것을 나타냅니다.