codeforces 228E

The vertices from the result call switched-on. Firstly, note that every vertex should be switched-on no more than once. Then, consider every edge (x, y) of color c. We want to make its color 1. So, if c = 1 we should switch on vertices x and y or don’t switch them on simultaneously. If c = 0 we should switch on x or y. So, consider some vertex v and try to switch it on or not. Thus, we can uniquely determine the state of every vertex of the same connected component as v. If we face some collision, we can’t get the solution, you should print Impossible. The solution can be realized using bfs with complexity O(N + M).