#D0072. 三值逻辑

三值逻辑

题目描述

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

在三值逻辑中,一个变量的值可能为:真(True\mathit{True},简写作 T\mathit{T})、假(False\mathit{False},简写作 F\mathit{F})或未确定(Unknown\mathit{Unknown},简写作 U\mathit{U})。

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

$$\lnot \mathit{T} = \mathit{F}, \lnot \mathit{F} = \mathit{T}, \lnot\mathit{U} = \mathit{U}. $$

现在小 L 有 nn 个三值逻辑变量 x1,,xnx_1,\cdots, x_n。小 L 想进行一些有趣的尝试,于是他写下了 mm 条语句。语句有以下三种类型,其中 \leftarrow 表示赋值:

  1. xivx_i \leftarrow v,其中 vvT,F,U\mathit{T}, \mathit{F}, \mathit{U} 的一种;
  2. xixjx_i \leftarrow x_j
  3. xi¬xjx_i \leftarrow \lnot x_j

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

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

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

输入格式

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

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

接下来,对于每组测试数据:

  • 输入的第一行包含两个整数 nnmm,分别表示变量个数和语句条数。
  • 接下来 mm 行,按运行顺序给出每条语句。
    • 输入的第一个字符 vv 描述这条语句的类型。保证 vvTFU+- 的其中一种。
    • vvTFU 的某一种时,接下来给出一个整数 ii,表示该语句为 xivx_i \leftarrow v
    • vv+,接下来给出两个整数 i,ji,j,表示该语句为 xixjx_i \leftarrow x_j
    • vv-,接下来给出两个整数 i,ji,j,表示该语句为 xi¬xjx_i \leftarrow \lnot x_j

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

0
3
1

提示

【样例解释 #1】

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

  • x2¬x1x_2 \leftarrow \lnot x_1
  • x3¬x2x_3 \leftarrow \lnot x_2
  • x1x3x_1 \leftarrow x_3

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

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

  • x2¬x1x_2 \leftarrow \lnot x_1
  • x3¬x2x_3 \leftarrow \lnot x_2
  • x1¬x3x_1 \leftarrow \lnot x_3

唯一的赋初值方案为 x1=x2=x3=Ux_1 = x_2 = x_3 = \mathit{U},共有 33Unknown\mathit{Unknown} 变量,故输出为 33

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

  • x2Tx_2 \leftarrow \mathit{T}
  • x2Ux_2 \leftarrow \mathit{U}

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

【样例解释 #2】

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

【样例解释 #3】

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

【样例解释 #4】

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

【数据范围】

对于所有测试数据,保证:

  • 1t61 \le t \le 61n,m1051 \le n,m \le 10 ^ 5
  • 对于每个操作,vvTFU+- 中的某个字符,1i,jn1 \le i,j \le n
测试点编号 n,mn,m\leq vv 可能的取值
1,21,2 1010 TFU+\mathit{TFU+-}
33 10310^3 TFU\mathit{TFU}
44 10510^5
55 10310^3 U+\mathit{U+}
66 10510^5
77 10310^3 +\mathit{+-}
88 10510^5
99 10310^3 TFU+\mathit{TFU+-}
1010 10510^5