#NOI2015A. 程序自动分析 (Automatic Program Analysis)
程序自动分析 (Automatic Program Analysis)
Description
In the process of automatic program analysis, it is often necessary to determine whether some constraints can be satisfied at the same time.
Consider a simplified version of the constraint satisfaction problem: suppose represent variables appearing in the program, and given are equality/inequality constraints of the form or . Please determine whether you can assign appropriate values to each variable so that all the given constraints are met simultaneously. For example, for the following constraints: $x_1 = x_2, \ x_2 = x_3, \ x_3 = x_4, \ x_1 \neq x_4$, these constraints are obviously impossible to be satisfied at the same time, so this problem should be judged as unsatisfiable. Given some constraint satisfaction problems, please judge them separately.
Input Format
The first line of the input file contains a positive integer , which indicates the number of problems to be judged. Note that these problems are independent of each other.
For each problem, there are several lines:
The first line contains a positive integer , which represents the number of constraints that need to be satisfied in the problem. In the next lines, each line includes three integers , describing an equality/inequality constraint, each integer separated by a single space. If , the constraint condition is ; if , the constraint condition is .
Output Format
The output file includes lines. The line of the output file contains a string YES
or NO
(without quotation marks, all uppercase letters). YES
means that the problem in the input can be satisfied, and NO
means that it cannot be satisfied.
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
NO
YES
Constraints
For all data, $1 \leq t \leq 10, \ 1 \leq n \leq 10^6, \ 1 \leq i,j \leq 10^9$.