Automated Program Analyzer

Let $x\_1, x\_2, x\_3, \dots$ be variables. $n$ constraints of form $x\_i = x\_j$ or $x\_i \ne x\_j$ are given. The task asks for whether it is possible to assign values to the variables so that all constraints can be satisfied. For example, if the constraints are $x\_1 = x\_2, x\_2 = x\_3, x\_3 = x\_4, x\_1 \ne x\_4$, then those constraints cannot be satisfied simultaneously.

The first line of the input is an integer $t$ representing the number of instances to solve. The instances are independent. For each instance, the first line is an integer $n$ representing the number of constraints to be satisfied. In the following $n$ lines, each line has three integers $i,j,e$ representing an equality/inequality constraint. If $e = 1$, the constraint shall be $x\_i = x\_j$. If $e = 0$, the constraint shall be $x\_i \ne x\_j$.

The output has $t$ lines. The $k$-th line of the output is a string YES or NO. Output YES if the constraints in that instance can be satisfied and NO otherwise.

• $1 \le n \le 100\\,000$
• $1 \le i, j \le 1\\,000\\,000\\,000$
• $1 \le t \le 10$
• $e \in \\{0,1\\}$