给一张 \(n\,(3\le n\le 10^5)\) 个点 \(m\,(2\le m\le 2\times 10^5)\) 条边的无向连通图，以及三个正整数 \(a,b,c\)，保证 \(a+b+c=n\)。你需要对每个点染成三种颜色中的一种，使得这三种颜色的点的个数分别为 \(a,b,c\)，且有两种颜色的点构成两个联、连通块。可能无解。
我们先考虑我们这两个连通块的大小应该为多少。我们不妨令 \(a\le b\le c\)，那么我们发现其实只要让 \(a\) 和 \(b\) 是连通块即可。因为如果是 \(c\) 是连通块，那么我们显然可以通过删掉部分节点的方式将其的大小缩小。
考虑到这一点，如果这是一棵树的话，那算法就简单了。我们考虑枚举一条边，如果边两边的 size 分别大于了 \(a\) 和 \(b\)，那就 YES 了。如果找不到的话，那显然就是 NO。
然后我们考虑图的情况，其实就是在这棵树上加了几条边。考虑到我们考虑这棵树是这张无向图的 dfs 树，这样这些新加进去的边就一定是返祖边，而不会存在横叉边的情况。我们先忽略这条边，如果找到了一边大于 \(a\) 一边大于 \(b\)，那一定 YES。我们考虑找不到的情况，这时候我们就可以用那几条返祖边进行调整。一种比较直接的调整方法是，考虑 \(x\) 与 \(f_x\)（\(x\) 父亲）的那条边，那我们可以将 \(x\) 子树中，存在返祖边为 \(x\) 祖先的那些子树加入到 \(f_x\) 所在的那个集合中。也就是用减少 \(x\) 所在连通块大小的代价换取 \(f_x\) 所在连通块大小的增加。让我们考虑对于一个 \(x\)，令 \(s_x\) 表示节点 \(x\) 的大小。由于我们调整的目的是为了让 \(f_x\) 所在连通块更大，所以我们考虑让 \(x\) 所在连通块不经过调整不能再小了，也就是 \(s_x\ge a\) 但对于 \(x\) 的任意一个儿子 \(t\)，都有 \(s_t<a\)。然后我们考虑进行调整。我们最终一定能找到一个临界，也就是不能继续调整了。这个时候有两种情况，第一种情况是，虽然还是有未加入 \(f_x\) 所在连通块的存在与之有返祖边联通的子树 \(t\)，但如果加入该子树，那么 \(x\) 所在连通块大小就小于 \(a\) 了，考虑到此时 \(x\) 所在连通块大小为 \(u\)，子树 \(t\) 大小为 \(v\)，我们有 \(\begin{cases}u\ge a\\u - v < a\\v < a\end{cases}\)，也即 \(a\le u < 2a\) 那么我们考虑 \(f_x\) 所在连通块的大小：\(n-u=a+b+c-u>a+b+c-2a=b+(c-a)\ge b\)。也就是说这种情况一定是 YES 的。然后我们考虑第二种情况，就是已经没有子树有可用的返祖边了，那这时候如果 \(f_x\) 所在连通块大小仍然小于 \(b\) 的话，那对于这个点，一定是不可能的了。那么，我们只要继续考虑其他的同样满足 \(s_x\ge a\) 且对于 \(x\) 的任意儿子 \(t\) 都有 \(s_t<a\) 的所有 \(x\) 即可。如果都不满足条件，那显然答案是 NO。这样复杂度 \(\mathcal{O}(n)\)。