P1955 [NOI2015] Program Automatic Analysis

During the implementation of automatic program analysis, it is often necessary to determine whether certain constraints can be satisfied simultaneously. Consider a simplified version of a constraint satisfaction problem: suppose $x_1, x_2, x_3, \cdots$ represent variables that appear in the program. Given $n$ constraints of the form $x_i = x_j$ or $x_i \neq x_j$, determine whether it is possible to assign an appropriate value to each variable so that all the constraints are satisfied simultaneously. For example, if the constraints in one problem are $x_1 = x_2, x_2 = x_3, x_3 = x_4, x_4 \neq x_1$, these constraints are clearly impossible to satisfy at the same time, so this problem should be judged as unsatisfiable. Now you are given several constraint satisfaction problems. Please determine each of them.

The first line contains a positive integer $t$, indicating the number of problems to judge. Note that these problems are independent of each other. For each problem, there are several lines: The first line contains a positive integer $n$, indicating the number of constraints that need to be satisfied in this problem. The next $n$ lines each contain three integers $i, j, e$, describing one equality/inequality constraint, with a single space between adjacent integers. If $e = 1$, then the constraint is $x_i = x_j$. If $e = 0$, then the constraint is $x_i \neq x_j$.

Output $t$ lines. On the $k$-th line, output the string YES or NO (all uppercase). YES means the $k$-th problem in the input is judged satisfiable, and NO means it is unsatisfiable.

[Sample Explanation 1] In the first problem, the constraints are $x_1 = x_2, x_1 \neq x_2$. These two constraints contradict each other, so they cannot be satisfied simultaneously. In the second problem, the constraints are $x_1 = x_2, x_1 = x_2$. These two constraints are equivalent and can be satisfied simultaneously. [Sample Explanation 2] In the first problem, there are three constraints: $x_1 = x_2, x_2 = x_3, x_3 = x_1$. It suffices to assign values so that $x_1 = x_2 = x_3$, and all constraints are satisfied. In the second problem, there are four constraints: $x_1 = x_2, x_2 = x_3, x_3 = x_4, x_4 \neq x_1$. From the first three constraints we can derive $x_1 = x_2 = x_3 = x_4$, but the last constraint requires $x_1 \neq x_4$, so it is unsatisfiable. [Constraints] All testdata ranges and characteristics are as follows: ::cute-table{tuack} | Test point id | Range of $n$ | Range of $i, j$ | Conventions | | :-: | :-: | :-: | :-: | | $1$ | $1 \le n \le 10$ | $1 \le i, j \le 10^4$ | $1 \le t \le 10$; $e \in \{0, 1\}$ | | $2$ | ^ | ^ | ^ | | $3$ | $1 \le n \le 100$ | ^ | ^ | | $4$ | ^ | ^ | ^ | | $5$ | $1 \le n \le 10^5$ | ^ | ^ | | $6$ | ^ | ^ | ^ | | $7$ | ^ | ^ | ^ | | $8$ | $1 \le n \le 10^5$ | $1 \le i, j \le 10^9$ | ^ | | $9$ | ^ | ^ | ^ | | $10$ | ^ | ^ | ^ | Translated by ChatGPT 5