Problem Description

Little L is learning Kleene three-valued logic today.

In three-valued logic, the value of a variable can be: true ($\mathit{True}$, abbreviated as $\mathit{T}$), false ($\mathit{False}$, abbreviated as $\mathit{F}$), or unknown ($\mathit{Unknown}$, abbreviated as $\mathit{U}$).

Logical operations can also be defined on three-valued logic. Since Little L is progressing very slowly, he has only learned the logical NOT operation $\lnot$, whose rules are:

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

Now Little L has $n$ three-valued logic variables $x_1,\cdots, x_n$. Little L wants to do something interesting, so he wrote down $m$ statements. There are three types of statements, where $\leftarrow$ denotes assignment:

1. $x_i \leftarrow v$, where $v$ is one of $\mathit{T}, \mathit{F}, \mathit{U}$;
2. $x_i \leftarrow x_j$;
3. $x_i \leftarrow \lnot x_j$.

At the beginning, Little L will assign initial values to these variables, and then run the $m$ statements in order.

Little L hopes that after executing all statements, the final values of all variables are the same as their initial values. Under this condition, Little L wants the number of variables whose initial values are $\mathit{Unknown}$ to be as small as possible.

In this problem, you need to help Little L find an initial assignment scheme with the minimum number of $\mathit{Unknown}$ variables, such that after executing all statements, the final values of all variables are equal to their initial values. Little L guarantees that, at least for all test cases in this problem, such an initial assignment scheme must exist.

Input Format

This problem contains multiple groups of testdata.

The first line of input contains two integers $c$ and $t$, representing the test point number and the number of testdata groups, respectively. For the samples, $c$ indicates that the sample has the same constraints as test point $c$.

Then, for each group of testdata:

• The first line contains two integers $n$ and $m$, representing the number of variables and the number of statements, respectively.
• The next $m$ lines give each statement in execution order.
  • The first character $v$ describes the type of the statement. It is guaranteed that $v$ is one of TFU+-.
  • If $v$ is one of TFU, then an integer $i$ follows, meaning the statement is $x_i \leftarrow v$.
  • If $v$ is +, then two integers $i,j$ follow, meaning the statement is $x_i \leftarrow x_j$.
  • If $v$ is -, then two integers $i,j$ follow, meaning the statement is $x_i \leftarrow \lnot x_j$.

Output Format

For each group of testdata, output one line with one integer, representing the minimum number of $\mathit{Unknown}$ variables among all initial assignment schemes that satisfy the condition.

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

Hint

[Sample Explanation #1]

In the first group of testdata, the $m$ statements in order are:

• $x_2 \leftarrow \lnot x_1$;
• $x_3 \leftarrow \lnot x_2$;
• $x_1 \leftarrow x_3$.

A valid initial assignment scheme is $x_1 = \mathit{T}, x_2 = \mathit{F}, x_3 = \mathit{T}$, with a total of $0$ $\mathit{Unknown}$ variables. Since no initial assignment can have fewer than $0$ $\mathit{Unknown}$ variables, the output is $0$.

In the second group of testdata, the $m$ statements in order are:

• $x_2 \leftarrow \lnot x_1$;
• $x_3 \leftarrow \lnot x_2$;
• $x_1 \leftarrow \lnot x_3$.

The only initial assignment scheme is $x_1 = x_2 = x_3 = \mathit{U}$, with a total of $3$ $\mathit{Unknown}$ variables, so the output is $3$.

In the third group of testdata, the $m$ statements in order are:

• $x_2 \leftarrow \mathit{T}$;
• $x_2 \leftarrow \mathit{U}$;

An initial assignment scheme that minimizes the number of $\mathit{Unknown}$ variables is $x_1 = \mathit{T}, x_2 = \mathit{U}$. The scheme $x_1 = x_2 = \mathit{U}$ is also valid, but it does not minimize the number of $\mathit{Unknown}$ variables.

[Sample Explanation #2]

This group of samples satisfies the conditions of test point $2$.

[Sample Explanation #3]

This group of samples satisfies the conditions of test point $5$.

[Sample Explanation #4]

This group of samples satisfies the conditions of test point $8$.

[Constraints]

For all testdata, it is guaranteed that:

• $1 \le t \le 6$, $1 \le n,m \le 10 ^ 5$;
• For each operation, $v$ is a character in TFU+-, and $1 \le i,j \le n$.

Test Point Number	$n,m\leq$	Possible values of $v$
$1,2$	$10$	$\mathit{TFU+-}$
$3$	$10^3$	$\mathit{TFU}$
$4$	$10^5$
$5$	$10^3$	$\mathit{U+}$
$6$	$10^5$
$7$	$10^3$	$\mathit{+-}$
$8$	$10^5$
$9$	$10^3$	$\mathit{TFU+-}$
$10$	$10^5$

Translated by ChatGPT 5