Задача М1147‍‍

Возьмём одну из заданных точек $a$‍‍ и рассмотрим все точки, соединённые с $a$‍‍ путём из данных отрезков. Если такой путь содержит чётное число (возможно, нуль) красных отрезков, то отнесём соответствующую точку к множеству $A$‍,‍ в частности, $a\in A$‍;‍ если же число красных отрезков на таком пути нечётно, то отнесём его конец к множеству $B$‍‍ (см. рисунок). Это правило разбиения корректно: если в некоторую точку $x$‍‍ можно было прийти из $a$‍‍ по двум разным путям, причём в одном из них было бы чётное, а в другом — нечётное число красных отрезков, то они составили бы замкнутый путь с нечётным числом красных отрезков, что по условию невозможно.

Ясно, что любой отрезок, соединяющий точки разных множеств, — красный, а любой отрезок, соединяющий две точки множества $A$‍,‍ — синий. Отрезок, соединяющий две точки $y$‍‍ и $z$‍‍ множества $B$‍‍ также синий, — если бы он был красным, то, присоединив его к пути из $a$‍‍ в $y$‍‍ с нечётным числом красных отрезков, мы получили бы путь из $a$‍‍ в $z$‍‍ с чётным числом красных отрезков.

Если есть ещё точки, с которыми точка $a$‍‍ вообще не связана никаким путём, — заданная конфигурация точек и отрезков состоит из нескольких связных компонент, — то можно взять по одной точке в каждой связной компоненте и для каждой из них построить требуемое разбиение.