Solving a in/equality constraint problem with graph search

Question

You are given a list of m constraints over n distinct variables x1, ..., xn. Each constraint is of one of the following two types.

1. An equality constraint of the form xi = xj for some i!=j.
2. An inequality constraint of the form xi!= xj for some i!=j.

I want to find an assignment, if it exists, for each variable such that it conforms to all the constraints using a graph search algorithm in O(m+n) time.

This reminds me of the graph colouring problem, however that only involves checking graph neighbours where as in any efficient graph I could think of, the nodes sharing a constraint may not be neighbours.

My first thought was to create a graph such that all nodes that equal are connected then use DFS to traverse each node and check if it has an inequality with a parent, however that doesn't seem very efficient as for every node (m) I have to traverse every inequality constraint (at most n) which brings me to nm time, where as DFS inherently has O(m+n)on an ideal representation.

Any clues?