$rt$ ,暂且不考虑均摊复杂度的问题,本题需要维护联通块(按秩合并的并查集?)以及每个联通块中的颜色(unordered_map),如何加入点应该是好解决的,问题是如何在与加点复杂度相同的条件下执行回滚操作?