题目描述

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

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

输入

本题的测试点包含有多组测试数据。 输入的第一行包含两个整数 $c$ 和 $t$，分别表示测试点编号和测试数据组数。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。 接下来，对于每组测试数据： • 输入的第一行包含两个整数 $n$ 和 $m$，分别表示变量个数和语句条数。 • 接下来 $m$ 行，按运行顺序给出每条语句。 – 输入的第一个字符 $v$ 描述这条语句的类型。保证 $v$ 为 $TFU+‐$ 的其中一种。 – 若 $v$ 为 $TFU$ 的某一种时，接下来给出一个整数 $i$，表示该语句为 $x_i$ ← $v$； – 若 $v$ 为 $+$，接下来给出两个整数 $i$, $j$，表示该语句为 $x_i$ ← $x_j$； – 若 $v$ 为 $‐$，接下来给出两个整数 $i$, $j$，表示该语句为 $x_i$ ← $¬x_j$。

输出

对于每组测试数据输出一行一个整数，表示所有符合条件的赋初值方案中，$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$ ← $¬x_1$； • $x_3$ ← $¬x_2$； • $x_1$ ← $x_3$。 一组合法的赋初值方案为 $x_1 = T$, $x_2 = F$, $x_3 = T$，共有 $0$ 个 $Unknown$ 变量。因为不存在赋初值方案中有小于 $0$ 个 $Unknown$ 变量，故输出为 $0$。 第二组测试数据中，$m$ 行语句依次为 • $x_2$ ← $¬x_1$； • $x_3$ ← $¬x_2$； • $x_1$ ← $¬x_3$。 唯一的赋初值方案为 $x_1 = x_2 = x_3 = U$，共有 $3$ 个 $Unknown$ 变量，故输出为 $3$。 【数据范围】 对于所有测试数据，保证： • $1 ≤ t ≤ 6$，$1 ≤ n, m ≤ 10^5$； • 对于每个操作，$v$ 为 $TFU+‐$ 中的某个字符，$1 ≤ i, j ≤ n$。

运算符说明

排版中的‐、−与半角-均表示逻辑非赋值。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。