A greedy solution will work. Store all the edges and take a mark[] array. The graph may or may not be connected. So, for each of it’s component run a DFS from any starting vertex say, X. Mark X=1. Now, in the DFS function, if the parent vertex is marked as 1, mark the children vertex with 2 else mark it with 1.

Now traverse the edge list and if any case occurs where mark[u]==mark[v] where uv denotes an edge between u and v, then simply print -1. This is because that edge can belong to only 1 subset. So, vertex cover condition is not followed.

If no such case arise, then simply put all the 1 marked vertices in one set and 2 marked vertices in the other.

My solution