Program Auto-analysis

Problem Description

When implementing program auto-analysis, we often need to decide whether a set of constraints can be satisfied simultaneously.

Consider a simplified constraint satisfaction problem: let $x_1,x_2,x_3,\dots$ be the variables appearing in a program. You are given $n$ constraints of the form $x_i = x_j$ or $x_i \neq x_j$ (variable equality / inequality) and must determine whether it is possible to assign a suitable value to every variable so that all the constraints are satisfied at the same time.

For example, if the constraints are $x_1 = x_2,\ x_2 = x_3,\ x_3 = x_4,\ x_1 \neq x_4$, it is clearly impossible to satisfy them all, so the answer should be "not satisfiable".

You are given several such constraint satisfaction problems; determine each of them.

Input Format

The first line of the input contains a positive integer $t$ $(1 \leq t \leq 10^5)$, the number of problems to judge. Note that these problems are independent of one another.

For each problem, the following lines are given:

• The first line contains a positive integer $n$ $(1 \leq n \leq 10^5)$, the number of constraints in this problem.
• The next $n$ lines each contain three integers $i, j, e$ $(1 \leq i, j \leq 10^9,\ 0 \leq e \leq 1)$, 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$.

$\sum n \leq 2.1 \times 10^5$

Output Format

The output file contains $t$ lines.

The $k$-th line of the output contains the string YES or NO. YES means the $k$-th problem in the input is judged to be satisfiable, and NO means it is not.

Sample Input

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

Sample Output

NO
YES

Constraints

• $1 \leq t \leq 10^5$
• $1 \leq n \leq 10^5$ for each problem, $\sum n \leq 2.1 \times 10^5$
• $1 \leq i, j \leq 10^9$, $0 \leq e \leq 1$
• The problems are independent of one another