B. 三值逻辑
time limit per test
1 second
memory limit per test
512 megabytes
input
tribool.in
output
tribool.out

小 L 今天学习了 Kleene 三值逻辑。 在三值逻辑中，一个变量的值可能为：真（$$$\mathit{True}$$$，简写作 $$$\mathit{T}$$$）、假（$$$\mathit{False}$$$，简写作 $$$\mathit{F}$$$）或未确定（$$$\mathit{Unknown}$$$，简写作 $$$\mathit{U}$$$）。 在三值逻辑上也可以定义逻辑运算。由于小 L 学习进度很慢，只掌握了逻辑非运算 $$$\lnot$$$，其运算法则为： $$$$$$\lnot \mathit{T} = \mathit{F}, \lnot \mathit{F} = \mathit{T}, \lnot\mathit{U} = \mathit{U}.$$$$$$ 现在小 L 有 $$$n$$$ 个三值逻辑变量 $$$x_1,\cdots, x_n$$$。小 L 想进行一些有趣的尝试，于是他写下了 $$$m$$$ 条语句。语句有以下三种类型，其中 $$$\leftarrow$$$ 表示赋值：

  1. $$$x_i \leftarrow v$$$，其中 $$$v$$$ 为 $$$\mathit{T}, \mathit{F}, \mathit{U}$$$ 的一种；
  2. $$$x_i \leftarrow x_j$$$；
  3. $$$x_i \leftarrow \lnot x_j$$$。
一开始，小 L 会给这些变量赋初值，然后按顺序运行这 $$$m$$$ 条语句。 小 L 希望执行了所有语句后，所有变量的最终值与初值都相等。在此前提下，小 L 希望初值中 $$$\mathit{Unknown}$$$ 的变量尽可能少。 在本题中，你需要帮助小 L 找到 $$$\mathit{Unknown}$$$ 变量个数最少的赋初值方案，使得执行了所有语句后所有变量的最终值和初始值相等。小 L 保证，至少对于本题的所有测试用例，这样的赋初值方案都必然是存在的。
Input

本题的测试点包含有多组测试数据。 输入的第一行包含两个整数 $$$c$$$ 和 $$$t$$$，分别表示测试点编号和测试数据组数。对于样例，$$$c$$$ 表示该样例与测试点 $$$c$$$ 拥有相同的限制条件。 接下来，对于每组测试数据：

  • 输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$，分别表示变量个数和语句条数。
  • 接下来 $$$m$$$ 行，按运行顺序给出每条语句。
    • 输入的第一个字符 $$$v$$$ 描述这条语句的类型。保证 $$$v$$$ 为 'TFU+-' 的其中一种。
    • 若 $$$v$$$ 为 'TFU' 的某一种时，接下来给出一个整数 $$$i$$$，表示该语句为 $$$x_i \leftarrow v$$$；
    • 若 $$$v$$$ 为 '+'，接下来给出两个整数 $$$i,j$$$，表示该语句为 $$$x_i \leftarrow x_j$$$；
    • 若 $$$v$$$ 为 '-'，接下来给出两个整数 $$$i,j$$$，表示该语句为 $$$x_i \leftarrow \lnot x_j$$$。
Output

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

Example
Input
1 3
3 3
- 2 1
- 3 2
+ 1 3
3 3
- 2 1
- 3 2
- 1 3
2 2
T 2
U 2
Output
0
3
1
Note

【样例解释 #1】

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

- $$$x_2 \leftarrow \lnot x_1$$$； - $$$x_3 \leftarrow \lnot x_2$$$； - $$$x_1 \leftarrow x_3$$$。

一组合法的赋初值方案为 $$$x_1 = \mathit{T}, x_2 = \mathit{F}, x_3 = \mathit{T}$$$，共有 $$$0$$$ 个$$$\mathit{Unknown}$$$ 变量。因为不存在赋初值方案中有小于 $$$0$$$ 个$$$\mathit{Unknown}$$$ 变量，故输出为 $$$0$$$。

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

- $$$x_2 \leftarrow \lnot x_1$$$； - $$$x_3 \leftarrow \lnot x_2$$$； - $$$x_1 \leftarrow \lnot x_3$$$。

唯一的赋初值方案为 $$$x_1 = x_2 = x_3 = \mathit{U}$$$，共有 $$$3$$$ 个$$$\mathit{Unknown}$$$ 变量，故输出为 $$$3$$$。

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

- $$$x_2 \leftarrow \mathit{T}$$$； - $$$x_2 \leftarrow \mathit{U}$$$；

一个最小化 $$$\mathit{Unknown}$$$ 变量个数的赋初值方案为 $$$x_1 = \mathit{T}, x_2 = \mathit{U}$$$。$$$x_1 = x_2 = \mathit{U}$$$ 也是一个合法的方案，但它没有最小化 $$$\mathit{Unknown}$$$ 变量的个数。

【数据范围】

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

  • $$$1 \le t \le 6$$$，$$$1 \le n,m \le 10 ^ 5$$$；
  • 对于每个操作，$$$v$$$ 为 'TFU+-'中的某个字符，$$$1 \le i,j \le n$$$。