三值逻辑

题目描述:

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

在三值逻辑中，一个变量的值可能为：真（$\mathit{True}$，简写作 $\mathit{T}$）、假（$\mathit{False}$，简写作 $\mathit{F}$）或未确定（$\mathit{Unknown}$，简写作 $\mathit{U}$）。

在三值逻辑上也可以定义逻辑运算。由于小 L 学习进度很慢，只掌握了逻辑非运算 $\mathrm{\neg }$，其运算法则为：
$$\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 \mathrm{\neg }{x}_j$。

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

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

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

输入格式:

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

输入的第一行包含两个整数 $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 \mathrm{\neg }{x}_j$。

输出格式:

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

样例输入:

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

提示:

【样例解释 #1】

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

- $x_2\leftarrow \mathrm{\neg }{x}_1$；
- $x_3\leftarrow \mathrm{\neg }{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 \mathrm{\neg }{x}_1$；
- $x_3\leftarrow \mathrm{\neg }{x}_2$；
- $x_1\leftarrow \mathrm{\neg }{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$。

| 测试点编号 | $n,m\le$ | $v$ 可能的取值 |
| :----------: | :----------: | :----------: |
| $1,2$ | $10$ | $\mathit{TFU}\mathit{+}\mathit{-}$ |
| $3$ | ${10}^3$ | $\mathit{TFU}$ |
| $4$ | ${10}^5$ | $\mathit{TFU}$ |
| $5$ | ${10}^3$ | $\mathit{U}\mathit{+}$ |
| $6$ | ${10}^5$ | $\mathit{U}\mathit{+}$ |
| $7$ | ${10}^3$ | $\mathit{+}\mathit{-}$ |
| $8$ | ${10}^5$ | $\mathit{+}\mathit{-}$ |
| $9$ | ${10}^3$ | $\mathit{TFU}\mathit{+}\mathit{-}$ |
| $10$ | ${10}^5$ | $\mathit{TFU}\mathit{+}\mathit{-}$ |

时间限制: 1000ms
空间限制: 512MB

---

来源: NOIP2023提高T2