Liars and Truth Tellers

A farmer has spent so much time with his cows that he has begun to understand their language. He notices that among his $N$ cows ($2 \le N \le 1000$), some always tell the truth and the rest always lie.

The farmer writes down $M$ statements ($1 \le M \le 10\,000$) made by the cows. Each statement has one of two forms:

• x y T — cow $x$ claims that cow $y$ always tells the truth.
• x y L — cow $x$ claims that cow $y$ always lies.

Every statement is about a pair of two different cows, and the same pair of cows may appear in several statements.

The farmer suspects that he copied some entries down incorrectly, so there may be no way to label every cow as a truth teller or a liar that is consistent with all $M$ statements. To salvage as much of the list as possible, find the largest value of $A$ for which some labeling of the $N$ cows as truth tellers or liars is consistent with the first $A$ statements.

• Line 1: two space-separated integers $N$ and $M$.
• Lines 2 to $M+1$: each line has the form x y T or x y L, describing one statement made by cow $x$ about cow $y$ ($1 \le x, y \le N$, $x \ne y$).

• Line 1: the largest value of $A$ such that some assignment of "truth teller" or "liar" to each of the $N$ cows is consistent with the first $A$ statements.

In the sample, statements 1 and 3 cannot both hold, but statements 1 and 2 can: let cows 1, 2, and 3 tell the truth and let cow 4 be a liar.