给一个 $O(n\log^2 n)$ 的做法（
问题可以看成给所有点染两种颜色使得任意一条边两个端点中至少有一个染黑色，至多有一条边两个端点都是黑色。注意到删掉两个端点都是黑色的边剩余的部分一定是一个二分图。因此问题转化为是否存在一条边使得删掉该边后图是二分图（对于一个二分图直接染色构造方案即可）。
这里考虑类似 [CF1442D Sum](https://www.luogu.com.cn/problem/CF1442D) 中的分治做法，递归判断删掉区间 $[l,r]$ 内的边后剩下的图是否是二分图，这里使用可撤销并查集判断二分图。具体递归时在进左区间前将右区间的边加进去，如果当且图不是二分图直接 return。递归右区间前将左区间的边加进去。递归到 $[l,l]$ 时就找到了删掉一条边是二分图的方案了。复杂度是 $O(n\log ^2n)$ 的。
by RyexAwl @ 2022-05-14 16:32:59
@[王学逸](/user/317459) 谢谢，大致懂了
by I_am_Accepted @ 2022-05-15 19:13:20
不过官方题解是线性复杂度的（
by I_am_Accepted @ 2022-05-15 19:13:49