P9869 [NOIP2023] Three-Valued Logic

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.

**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$.

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.

**[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$ | $\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+-}$ | Translated by ChatGPT 5