Как два пальца об асфальт

У этой задачи оказалось много решений. Первоначально предполагалось решение, которое решало систему равенств по модулю 2, используя алгоритм Гаусса. Расскажем другое простое решение.

Вершины, которые мы возьмем в ответ, назовем включенными. Во-первых, очевидно, что каждую вершину мы включим не более одного раза. Теперь посмотрим на произвольное ребро (x, y) цвета c. Нам нужно, чтобы его цвет в результате равнялся 1. Если c = 1, нужно либо не включать вершины x и y, либо нужно их обе включить. Если c = 0, нужно включить либо x, либо y. Таким образом, если мы рассмотрим произвольную вершину v и переберем, включим ее или нет, то можно однозначно восстановить, какие вершины придется включить в компоненте связности вершины v. Если в некоторый момент у нас возникнет коллизия, мы выбрали неправильный цвет у вершины v. Если хотя бы одну компоненту покрасить не удастся, нужно вывести Impossible. Это можно реализовать за O(N + M) серией поисков в ширину.