Constraint Satisfaction: Equalities and Inequalities

This problem involves checking whether a set of equality and inequality constraints among variables can be simultaneously satisfied. The constraints are given in the form of $x_i = x_j$ or $x_i \neq x_j$, where $x_i$ represents a variable. The task is to determine if there exists an assignment of values to the variables such that all conditions hold true.

For example, consider the constraints: $x_1=x_2$, $x_2=x_3$, $x_3=x_4$, $x_4\neq x_1$. Since these constraints are mutually contradictory, the answer should be NO.

inputFormat

The first line contains an integer T representing the number of test cases. For each test case:

• The first line contains an integer n, the number of constraints.
• Each of the next n lines contains a constraint in one of the following forms: x_i=x_j or x_i\neq x_j, where i and j are positive integers.

outputFormat

For each test case, output a single line: YES if it is possible to assign values to the variables to satisfy all constraints, or NO if it is not possible.

sample

1
4
x1=x2
x2=x3
x3=x4
x4!=x1

NO