{"raw_statement":[{"iden":"statement","content":"小 L 今天学习了 Kleene 三值逻辑。\n\n在三值逻辑中，一个变量的值可能为：真（$\\mathit{True}$，简写作 $\\mathit{T}$）、假（$\\mathit{False}$，简写作 $\\mathit{F}$）或未确定（$\\mathit{Unknown}$，简写作 $\\mathit{U}$）。\n\n在三值逻辑上也可以定义逻辑运算。由于小 L 学习进度很慢，只掌握了逻辑非运算 $\\lnot$，其运算法则为：\n$$\\lnot \\mathit{T} = \\mathit{F}, \\lnot \\mathit{F} = \\mathit{T}, \\lnot\\mathit{U} = \\mathit{U}.$$\n\n现在小 L 有 $n$ 个三值逻辑变量 $x_1,\\cdots, x_n$。小 L 想进行一些有趣的尝试，于是他写下了 $m$ 条语句。语句有以下三种类型，其中 $\\leftarrow$ 表示赋值：\n\n1. $x_i \\leftarrow v$，其中 $v$ 为 $\\mathit{T}, \\mathit{F}, \\mathit{U}$ 的一种；\n2. $x_i \\leftarrow x_j$；\n3. $x_i \\leftarrow \\lnot x_j$。\n\n一开始，小 L 会给这些变量赋初值，然后按顺序运行这 $m$ 条语句。\n\n小 L 希望执行了所有语句后，所有变量的最终值与初值都相等。在此前提下，小 L 希望初值中 $\\mathit{Unknown}$ 的变量尽可能少。\n\n在本题中，你需要帮助小 L 找到 $\\mathit{Unknown}$ 变量个数最少的赋初值方案，使得执行了所有语句后所有变量的最终值和初始值相等。小 L 保证，至少对于本题的所有测试用例，这样的赋初值方案都必然是存在的。"},{"iden":"input","content":"**本题的测试点包含有多组测试数据。**\n\n输入的第一行包含两个整数 $c$ 和 $t$，分别表示测试点编号和测试数据组数。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。\n\n接下来，对于每组测试数据：\n\n- 输入的第一行包含两个整数 $n$ 和 $m$，分别表示变量个数和语句条数。\n- 接下来 $m$ 行，按运行顺序给出每条语句。\n  - 输入的第一个字符 $v$ 描述这条语句的类型。保证 $v$ 为 `TFU+-` 的其中一种。\n  - 若 $v$ 为 `TFU` 的某一种时，接下来给出一个整数 $i$，表示该语句为 $x_i \\leftarrow v$；\n  - 若 $v$ 为 `+`，接下来给出两个整数 $i,j$，表示该语句为 $x_i \\leftarrow x_j$；\n  - 若 $v$ 为 `-`，接下来给出两个整数 $i,j$，表示该语句为 $x_i \\leftarrow \\lnot x_j$。"},{"iden":"output","content":"对于每组测试数据输出一行一个整数，表示所有符合条件的赋初值方案中，$\\mathit{Unknown}$ 变量个数的最小值。"},{"iden":"note","content":"**【样例解释 #1】**\n\n第一组测试数据中，$m$ 行语句依次为\n\n- $x_2 \\leftarrow \\lnot x_1$；\n- $x_3 \\leftarrow \\lnot x_2$；\n- $x_1 \\leftarrow x_3$。\n\n一组合法的赋初值方案为 $x_1 = \\mathit{T}, x_2 = \\mathit{F}, x_3 = \\mathit{T}$，共有 $0$ 个 $\\mathit{Unknown}$ 变量。因为不存在赋初值方案中有小于 $0$ 个 $\\mathit{Unknown}$ 变量，故输出为 $0$。\n\n第二组测试数据中，$m$ 行语句依次为\n\n- $x_2 \\leftarrow \\lnot x_1$；\n- $x_3 \\leftarrow \\lnot x_2$；\n- $x_1 \\leftarrow \\lnot x_3$。\n\n唯一的赋初值方案为 $x_1 = x_2 = x_3 = \\mathit{U}$，共有 $3$ 个 $\\mathit{Unknown}$ 变量，故输出为 $3$。\n\n第三组测试数据中，$m$ 行语句依次为\n\n- $x_2 \\leftarrow \\mathit{T}$；\n- $x_2 \\leftarrow \\mathit{U}$；\n\n一个最小化 $\\mathit{Unknown}$ 变量个数的赋初值方案为 $x_1 = \\mathit{T}, x_2 = \\mathit{U}$。$x_1 = x_2 = \\mathit{U}$ 也是一个合法的方案，但它没有最小化 $\\mathit{Unknown}$ 变量的个数。\n\n**【样例解释 #2】**\n\n该组样例满足测试点 $2$ 的条件。\n\n**【样例解释 #3】**\n\n该组样例满足测试点 $5$ 的条件。\n\n**【样例解释 #4】**\n\n该组样例满足测试点 $8$ 的条件。\n\n**【数据范围】**\n\n对于所有测试数据，保证：\n\n- $1 \\le t \\le 6$，$1 \\le n,m \\le 10 ^ 5$；\n- 对于每个操作，$v$ 为 `TFU+-` 中的某个字符，$1 \\le i,j \\le n$。\n\n| 测试点编号 | $n,m\\leq$ | $v$ 可能的取值 |\n| :----------: | :----------: | :----------: |\n| $1,2$ | $10$ | $\\mathit{TFU+-}$ |\n| $3$ | $10^3$ | $\\mathit{TFU}$ |\n| $4$ | $10^5$ | $\\mathit{TFU}$ |\n| $5$ | $10^3$ | $\\mathit{U+}$ |\n| $6$ | $10^5$ | $\\mathit{U+}$ |\n| $7$ | $10^3$ | $\\mathit{+-}$ |\n| $8$ | $10^5$ | $\\mathit{+-}$ |\n| $9$ | $10^3$ | $\\mathit{TFU+-}$ |\n| $10$ | $10^5$ | $\\mathit{TFU+-}$ |"}],"translated_statement":null,"sample_group":[["1 3\n3 3\n- 2 1\n- 3 2\n+ 1 3\n3 3\n- 2 1\n- 3 2\n- 1 3\n2 2\nT 2\nU 2\n","0\n3\n1\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}