考慮一顆樹怎么染色。

每個子節(jié)點染成邊的顏色，如果與父親節(jié)點相同，就隨便染色（這條邊的限制已經(jīng)被父親節(jié)點滿足）。

那么一定可以染色。

所以把原圖跑最小生成樹再按上述方法染色即可。

倘若原圖不連通，那么無解。