#3889. [USACO13JAN] Liars and Truth Tellers B

[USACO13JAN] Liars and Truth Tellers B

题目描述

农夫约翰的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。