Here’s a problem that occurs in automatic program analysis. for a set of variables x1, . . , xn, you are given some equality constraints, of the form xi = xj and some disequality constraints, of the form xi 6= xj . is it possible to satisfy all of them? example: x1 = x2, x2 = x3, x3 = x4, x1 6= x4 cannot be satisfied. give an efficient algorithm that takes as input m constraints across n variables and determines if they can or cannot be satisfied. for full credit, your running time must be o(m log n) ; there is a solution that is faster than θ(m log n), but you do not need to come up with it for full credit.