Problem Description

In the process of implementing program automatic analysis, it is often necessary to determine whether some constraint conditions can be simultaneously satisfied.

Consider a simplified version of a constraint satisfaction problem: Suppose $x_1, x_2, x_3, \cdots$ represent variables appearing 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 appropriate values to each variable such that all the constraints are simultaneously satisfied. For example, a set of constraints might be: $x_1 = x_2, x_2 = x_3, x_3 = x_4, x_4 \neq x_1$. These constraints are clearly impossible to satisfy simultaneously, so this problem should be judged as unsatisfiable.

Now, given some constraint satisfaction problems, please determine them individually.

Input Format

The first line of the input contains a positive integer $t$, indicating the number of problems to be determined. 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 to be satisfied in this problem. The next $n$ lines each include three integers $i, j, e$, describing a constraint condition, with integers separated by a single space. If $e = 1$, the constraint is $x_i = x_j$. If $e = 0$, the constraint is $x_i \neq x_j$.

Output Format

The output includes $t$ lines.

The $k$-th line of the output file should output a string YES or NO (all letters in uppercase), where YES indicates that the $k$-th problem in the input can be satisfied, and NO indicates that it cannot be satisfied.

Sample Input and Output

Input Sample #1

2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

Output Sample #1

NO
YES

Input Sample #2

2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0

Output Sample #2

YES
NO

Notes

Sample Explanation 1

In the first problem, the constraints are: $x_1 = x_2, x_1 \neq x_2$. These two constraints are contradictory, 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$. Assigning values such that $x_1 = x_2 = x_3$ will satisfy all constraints simultaneously.

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$. The first three constraints imply $x_1 = x_2 = x_3 = x_4$, but the last constraint requires $x_1 \neq x_4$, making it impossible to satisfy.

Data Range

The range and characteristics of all test data are as follows:

Correction: For test points $8 \sim 10$, the constraints on $i, j$ are $1 \leq i, j \leq 10^9$, not $10^{10}$ as shown in the image.

见题面 Input 部分

见题面 Output 部分