P9869 [NOIP2023] 三值逻辑

小 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 保证，至少对于本题的所有测试用例，这样的赋初值方案都必然是存在的。

无

无

**【样例解释 #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}$ 变量的个数。 **【样例解释 #2】** 该组样例满足测试点 $2$ 的条件。 **【样例解释 #3】** 该组样例满足测试点 $5$ 的条件。 **【样例解释 #4】** 该组样例满足测试点 $8$ 的条件。 **【数据范围】** 对于所有测试数据，保证： - $1 \le t \le 6$，$1 \le n,m \le 10 ^ 5$； - 对于每个操作，$v$ 为 `TFU+-` 中的某个字符，$1 \le i,j \le n$。 | 测试点编号 | $n,m\leq$ | $v$ 可能的取值 | | :----------: | :----------: | :----------: | | $1,2$ | $10$ | $\mathit{TFU+-}$ | | $3$ | $10^3$ | $\mathit{TFU}$ | | $4$ | $10^5$ | $\mathit{TFU}$ | | $5$ | $10^3$ | $\mathit{U+}$ | | $6$ | $10^5$ | $\mathit{U+}$ | | $7$ | $10^3$ | $\mathit{+-}$ | | $8$ | $10^5$ | $\mathit{+-}$ | | $9$ | $10^3$ | $\mathit{TFU+-}$ | | $10$ | $10^5$ | $\mathit{TFU+-}$ |