25077번 - 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\}$

힌트