啥都想不出来的我是不是废了/dk
这道题考的主要是构造 而我想的主要是乱搞。
一个很假很假的做法：直接暴力4种颜色染色 我也不知道对不对。。 不过成功的话一定是对的。
然后考虑奇环的问题 一个很假很假的做法 建立出dfs树然后 然后利用返祖边+倍增做奇环的问题 主要考察环上所有的点的入度都>2。
显然 很多环都没有被便利到 所以这个做法是很假的。
好像多random几次能A？当然不行！接下来是否联通也存在问题 这个做法假死了 当然如果不嫌麻烦可以check且再次随机 暴力出奇迹嘛~！
然而水到了60
考虑正解 容易想到正解一定是两种解其中的一个 第一个解没有什么好的处理方法。
考虑奇环->二分图 那么其实我们可以先随便找到一棵树 然后先保证联通看剩下的东西是否是一个二分图。
如果不是 那么就存在奇环了 去掉且此时是联通的 如果不存在显然树可以用两个颜色染色 二分图也是如此 那么四颜色染色就派上用场了。
所以这个问题是一定有解的 至此问题得到解决。
考虑选取的树不同是否对答案造成影响 显然不会 因为这种构造方法使得什么情况都有解。
我也只能甘拜下风了。。