In the process of implementing program automatic analysis, it is often necessary to determine whether a set of constraints can be satisfied simultaneously.

Consider a simplified version of a constraint satisfaction problem: suppose $x_1, x_2, x_3, \dots$ represent variables appearing in a 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 given constraints are satisfied simultaneously. For example, if the constraints in a problem are $x_1 = x_2, x_2 = x_3, x_3 = x_4, x_1 \neq x_4$, these constraints are clearly impossible to satisfy simultaneously, so this problem should be determined as unsatisfiable.

Now, given several constraint satisfaction problems, please determine each of them.

Input

The input is read from the file prog.in.

The first line of the input file contains a single positive integer $t$, representing the number of problems to be determined. Note that these problems are independent of each other.

For each problem, it contains several lines: The first line contains a single positive integer $n$, representing the number of constraints to be satisfied in this problem. The next $n$ lines each contain three integers $i, j, e$, describing one equality/inequality constraint, with adjacent 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

The output is written to the file prog.out.

The output file includes $t$ lines. The $k$-th line of the output file should contain the string "YES" or "NO" (without quotes, all letters uppercase). "YES" indicates that the $k$-th problem in the input is satisfiable, and "NO" indicates that it is unsatisfiable.

Examples

Input 1

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

Output 1

NO
YES

Note 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_2 = x_1$. These two constraints are equivalent and can be satisfied simultaneously.

Input 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 2

YES
NO

Note 2

In the first problem, there are three constraints: $x_1 = x_2, x_2 = x_3, x_3 = x_1$. By assigning values such that $x_1 = x_2 = x_3$, all constraints can be satisfied simultaneously. In the second problem, there are four constraints: $x_1 = x_2, x_2 = x_3, x_3 = x_4, x_1 \neq x_4$. From the first three constraints, we can deduce $x_1 = x_2 = x_3 = x_4$, but the last constraint requires $x_1 \neq x_4$, so it cannot be satisfied.

Input 3

See prog/prog.in and prog/prog.ans in the contestant directory.

Constraints

The range and characteristics of all test data are shown in the table below: