(12%) For a set of variables $x_1, x_2, \ldots, x_n$, you are given some equality constraints, of the form "$x_i = x_j$" and some disequality constraints, of the form "$x_i \ne x_j$". Is it possible to satisfy all of them? For instance, the constraints:

$x_1 = x_2, x_2 = x_3, x_3 = x_4, x_1 \ne x_4$

cannot be satisfied. Give an efficient algorithm that takes as input m constraints over n variables and decides whether the constraints can be satisfied. Describe the data structure used by your algorithm, and analysis the time complexity of your algorithm.