#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 x1,x2,x3,x_1, x_2, x_3,\ldots represent variables appearing in the program, and given are equality/inequality constraints of the form xi=xjx_i =x_j or xixjx_i \neq x_j. 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 tt, 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 nn, which represents the number of constraints that need to be satisfied in the problem. In the next nn lines, each line includes three integers i,j,ei, j, e, describing an equality/inequality constraint, each integer separated by a single space. If e=1e = 1, the constraint condition is xi=xjx_i = x_j; if e=0e = 0, the constraint condition is xixjx_i \neq x_j​.

Output Format

The output file includes tt lines. The kthk^{th} line of the output file contains a string YES or NO (without quotation marks, all uppercase letters). YES means that the kthk^{th} 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$.