1). Use depth-first search
2). Use local variable for color in dfs procedure

dfs is enough, but it's better to store graph using compliance matrix, so keeping it in this way, your dfs will visit all nodes (1) and only when current node is already colored (2). If some of node, that we can go fro current is already colored and it has the same color, so -1 should be returned.