problem & blog。

题解代码都长得离谱，2k 代码了解一下！

如果我码风比较压行还可以 2k 以内，但是很不幸我是空格 + 大括号换行流。

不妨设 $a \le b \le c$，如果能使 $C$ 联通，那么从中取出一个 $A$ 或 $B$ 的连通块也是平凡的，所以只考虑 $A,B$。

考虑树的情况。要找到一条边 $(u,v)$ 满足 $u$ 那边的子树的 $siz\ge a$，$v$ 那边的子树的 $siz \ge b$。

容易发现 $a\le b\le \dfrac n2$，联想到重心，它的性质是 $\forall siz\le \dfrac n2$，所以只需要枚举与重心相连的边，如果能找到一个子树把 $A$ 塞进去，那么 $n-siz>n-\dfrac n2>\dfrac n2$，很容易就能把 $B$ 塞进去。找不到就是无解。

回到简单图。上面的 Special Task 提示我们建 $\text{DFS}$ 树，并找到它的重心。下文令 $siz_i$ 表示重心相邻的那些点的子树。

如果 $\exists siz_i \ge a$，直接按照树的方法构造即可。否则，考虑第一个子树，有一些其他的子树会与它相连。如果这些相连的子树都算上了，还是没法干掉 $A$，那么必须动用两次重心了，无解。

令 $S$ 表示干掉 $A$ 需要用到的点集。可以认为这个过程是一个一个看子树，当 $\sum\limits_S siz_i$ 成功干掉 $A$，立刻终止。由于 $\forall siz_i < a$，故 $\sum\limits_S siz_i < 2a$。继续化简，$n=a+b+c>2a+b>\sum\limits_S siz_i +b$，所以 $b<n-\sum\limits_S siz_i$，也就是说必定可以干掉 $B$。

输出即可。注意调换了 $a,b,c$ 满足 $a\le b\le c$ 后，输出也要调整一下。

代码，时间复杂度 $O(n+m)$。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int dict[4] = {0, 1, 2, 3};
void sortt(int &a, int &b, int &c) {if (a > b) swap(a, b), swap(dict[1], dict[2]); if (a > c) swap(a, c), swap(dict[1], dict[3]); if (b > c) swap(b, c), swap(dict[2], dict[3]);}
namespace T { //Tree
	struct Edge {int now, nxt;} e[N << 2];
	int head[N], cur;
	void add(int u, int v) {e[++cur].now = v, e[cur].nxt = head[u], head[u] = cur;}
}
struct Edge {int now, nxt;} e[N << 2];
int head[N], cur;
void add(int u, int v) {e[++cur].now = v, e[cur].nxt = head[u], head[u] = cur;}
int n, m, A, B, C, fath[N];
bool vis[N]; int siz[N], root = -1; //root : 重心
void getroot(int u, int fa)
{
	fath[u] = fa;
	vis[u] = true, siz[u] = 1; int mx = 0;
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].now;
		if (vis[v]) continue;
		T::add(u, v), T::add(v, u), getroot(v, u), siz[u] += siz[v], mx = max(mx, siz[v]);
	}
	mx = max(mx, n - siz[u]); if (mx <= n / 2) root = u;
}
int ans[N];
void dfs(int u, int fa, int col, int &siz)
{
	if (!u || !siz) return;
	ans[u] = col, siz--;
	for (int i = T::head[u]; i; i = T::e[i].nxt) {int v = T::e[i].now; if (v != fa && !ans[v]) dfs(v, u, col, siz);}
}
void dfsAll(int u, int fa, int col, int &siz)
{
	if (!u || !siz) return;
	for (int i = T::head[u]; i; i = T::e[i].nxt)
		{int v = T::e[i].now; if (v != fa) dfsAll(v, u, col, siz);}
	for (int i = head[u]; i; i = e[i].nxt)
		{int v = e[i].now; if (!ans[v]) dfs(v, u, col, siz);}
}

void NO() {for (int i = 1; i <= n; i++) printf("0 "); exit(0);}
void answer() {for (int i = 1; i <= n; i++) printf("%d ", dict[ans[i] ? ans[i] : 3]); exit(0);}
int main()
{
    scanf("%d%d%d%d%d", &n, &m, &A, &B, &C), sortt(A, B, C);
	while (m--) {int u, v; scanf("%d%d", &u, &v), u++, v++; add(u, v), add(v, u);}

	getroot(1, 0);
	siz[fath[root]] = n - siz[root];
	ans[root] = 1;
	for (int i = T::head[root]; i; i = T::e[i].nxt)
	{
		int v = T::e[i].now;
		if (siz[v] >= A) {dfs(v, root, 1, A), dfs(root, 0, 2, B), answer();}
	}
	dfs(fath[root], 0, 1, A), dfsAll(fath[root], root, 1, A);
	if (A) NO(); else dfs(root, 0, 2, B), answer();
    return 0;
}