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