题目描述

农夫约翰的N头奶牛（2 ≤ N ≤ 1000）中，有些总是说真话，有些总是说谎。约翰记录了M条奶牛之间的陈述（1 ≤ M ≤ 10,000），每条陈述格式为：

• "x y T"：表示奶牛x声称奶牛y总是说真话
• "x y L"：表示奶牛x声称奶牛y总是说谎

每条陈述涉及两头不同的奶牛，且同一对奶牛可能出现在多条陈述中。由于约翰可能记录有误，可能存在无法将所有奶牛划分为说真话者和说谎者的情况。

请计算最大的A值，使得前A条陈述能够与某种奶牛分类方式（说真话/说谎）相符合。

输入格式

第一行：两个整数N和M

接下来M行：每行一条陈述，格式为"x y T"或"x y L"

输出格式

一个整数，表示满足条件的最大A值

输入输出样例

输入 #1

4 3
1 4 L
2 3 T
4 1 T

输出 #1

2

样例解释

4头奶牛和3条陈述：

1. 奶牛1说奶牛4说谎
2. 奶牛2说奶牛3说真话
3. 奶牛4说奶牛1说真话

分析：

• 前两条陈述可以同时满足（例如让奶牛1-3说真话，奶牛4说谎）
• 加入第三条陈述会导致矛盾（如果奶牛4说谎，则它说"奶牛1说真话"是假话，意味着奶牛1实际说谎，但这样奶牛1说"奶牛4说谎"就变成真话，矛盾）

因此最大A值为2。