考虑我们判定二分图染色的经典算法：
染色。
我们把所有不同颜色块之间的边都保存下来。
只在图中保留相同颜块之间的边，并对其染色。
我们考虑记\(g_i\)为一个点的所在联通块编号，\(f_i\)为他在染色时被染的颜色。
我们只考虑所有有不同颜色块连边的颜色块并计算那对颜色块是否有可能成为二分图。
我们考虑所有在颜色\((u,v)\)的边。
如果两边的端点的\(f_i\)相同，则在新图中创建一个新点，并和两端点在的联通块连边。
否则直接把联通块连边。
然后对新图进行二分图染色判断，如果染色无冲突则可以。
复杂度\(O(n + m log m)\)