题解：POI 2011 Garbage

核心思路

每条边初始颜色 s，目标颜色 t

定义 need = s XOR t，若 need=1 表示需要翻转奇数次，need=0 表示不需要翻转

只考虑 need=1 的边构成的图 G'

关键结论

如果 G' 中所有点的度数为偶数 → 存在简单环覆盖所有 need=1 的边 否则 → 无解

算法步骤

输入 n,m，标记所有 need=1 的边，记录每个点度数

检查所有点度数是否为偶数，否则输出 NIE

对 G' 的每个连通分量找欧拉回路

将欧拉回路切割成简单环（当遇到重复顶点时切割）

输出环的数量和每个环

时间复杂度 O(n + m)