#10000032. 【NOIP 2023】三值逻辑（tribool）

提交源程序文件名

【题目描述】

小 L 今天学习了 Kleene 三值逻辑。

在三值逻辑中，一个变量的值可能为：真（，简写作 ）、假（，简写作 ）或未确定（，简写作 ）。

在三值逻辑上也可以定义逻辑运算。由于小 L 学习进度很慢，只掌握了逻辑非运算 ，其运算法则为：

现在小 L 有 个三值逻辑变量 。小 L 想进行一些有趣的尝试，于是他写下了 条语句。语句有以下三种类型，其中 表示赋值：

1. ，其中 为 的一种；
2. ；
3. 。

一开始，小 L 会给这些变量赋初值，然后按顺序运行这 条语句。

小 L 希望执行了所有语句后，所有变量的最终值与初值都相等。在此前提下，小 L 希望初值中 的变量尽可能少。

在本题中，你需要帮助小 L 找到 变量个数最少的赋初值方案，使得执行了所有语句后所有变量的最终值和初始值相等。小 L 保证，至少对于本题的所有测试用例，这样的赋初值方案都必然是存在的。

【输入格式】

从文件 中读入数据。

本题的测试点包含有多组测试数据。

输入的第一行包含两个整数 和 ，分别表示测试点编号和测试数据组数。对于样例， 表示该样例与测试点 拥有相同的限制条件。

接下来，对于每组测试数据：

• 输入的第一行包含两个整数 和 ，分别表示变量个数和语句条数。
• 接下来 行，按运行顺序给出每条语句。

  • 输入的第一个字符 描述这条语句的类型。保证 为 TFU+‐ 的其中一种。

  • 若 为 TFU 的某一种时，接下来给出一个整数 ，表示该语句为 ；

  • 若 为 +，接下来给出两个整数 ，表示该语句为 ；

  • 若 为 ‐，接下来给出两个整数 ，表示该语句为 。

【输出格式】

输出到文件 中。

对于每组测试数据输出一行一个整数，表示所有符合条件的赋初值方案中， 变量个数的最小值。

【样例 输入】

1 3
3 3
‐ 2 1
‐ 3 2
+ 1 3
3 3
- 2 1
‐ 3 2
‐ 1 3
2 2
T 2
U 2

【样例 输出】

0
3
1

【样例 解释】

第一组测试数据中， 行语句依次为

• ；
• ；
• 。

一组合法的赋初值方案为 ，共有 个 变量。因为不存在赋初值方案中有小于 个 变量，故输出为 。

第二组测试数据中， 行语句依次为

• ；
• ；
• 。

唯一的赋初值方案为 ，共有 个 变量，故输出为 。

第三组测试数据中， 行语句依次为

• ；
• ；

一个最小化 变量个数的赋初值方案为 。 也是一个合法的方案，但它没有最小化 变量的个数。

【样例 】

见选手目录下的 与 。

该组样例满足测试点 的条件。

【样例 】

见选手目录下的 与 。

该组样例满足测试点 的条件。

【样例 】

见选手目录下的 与 。

该组样例满足测试点 的条件。

【数据范围】

对于所有测试数据，保证：

• ，；

• 对于每个操作， 为 TFU+‐ 中的某个字符，。