这个题对我来说可以算是超出了我的能力范围
被学长拿来教我做构造，构造题真简单，构造题真是人，构造题真能手切。。。
首先对于本题，必须要知道dfs树这东西，就是在一个图中得到一个树，
简单来说就是吧所有的边分成树边和非树边，所有的n-1个树边会把所有点连接成一颗树
这个在实现上就是一个dfs就好了
这里有一个小小的性质，在一个dfs树中，所有的非树边一定不是横叉边
意思就是所有的边连接的两个点一定是祖先后代关系
那么这个题就可以做了
你会发现这a,b,c并没有特殊的要求，所以我们选择这其中较小的那两个一定是优的
所以我们直接扔掉最大的那个，这时候你会发现
为了保证我们很顺利的找到答案，我们必须要找到树的重心，
因为在重心两侧，子树的大小一定小于等于\(\frac{n}{2}\),而a，b的大小又小于等于\(\frac{n}{3}\)
这样的话，我们只要保存这个重心，我们可以任意连接子树，从而一定可以满足\(a,b\)的其中一个
而剩下的子树中的节点数又一定大于a，这样为我们找到答案提供了很大的方便
那么我们一定先满足\(b\)，因为我们要是想凑出a来一定是比b更容易，那么我们接下来的重点就是要找a
首先我们看\(m=n-1\)的情况,这样的话本来就是一棵树，直接找到重心，判断是不是有子树的大小大于a，如果有 ，那么就有解，没有的话，就无解呗
因为你没有别的边可以连接另外的子树，所以你当前的子树就你你可以找到的所有可以作为a的联通块
而b可以通过重心连接，不需要考虑
那么这时候你会发现，如果是图的话，那就可以有别的边来连接？？虽然不可以连接在dfs树上的子树，
但是别忘了，在dfs树上，它的祖先也是他的子树，所以我们只要不断的去连接和它祖先有连边的子树，并且将大小加和
如果能够得到一个大小为a的联通块，那就有解，当然这时候你并没有选重心，b仍然是合法的
我们来看这里的重心有什么用，这个重心首先保证了你有一堆大小\(<=\frac{n}{2}\)的子树
这样的话，你一定可以凑出一个b来，而重心又在一定程度上帮你将整张图分为两部分
一个是那一堆子树，一个是祖先那边的节点，这就是构造的意义所在
构造你想要的条件来解决一般问题
还有一些要注意的情况，
有可能在图中，你并不能找到合法的反祖边，但是呢，有一颗子树的大小是合法的，
这个时候就要向树的做法一样了，我要去判断一下每一颗子树的大小
还有输出的时候，千万不要找到一颗子树就开始从他的根节点遍历
因为你是从有和祖先连边的那个点出发才可以联通的啊，要从他开始
我的代码中imp这个数组就是干这个活的
AC_code
#include <bits/stdc++.h>
using namespace std;
#define re register int
const int N = 1e5 + 5;
const int M = 2e5 + 5;
int n, m;
pair<int, int> a[4];
int fr[M * 2], to[M * 2], nxt[M * 2], head[N], rp = 1;
void add_edg(int x, int y) {
to[++rp] = y;
fr[rp] = x;
nxt[rp] = head[x];
head[x] = rp;
}
int fa[N], dep[N], siz[N], rt, mn = 0x3f3f3f3f;
bool vis[N], pd[M * 2];
void dfs(int x) {
vis[x] = true;
siz[x] = 1;
int mx = 0; for (re i = head[x]; i; i = nxt[i]) {
int y = to[i]; if (vis[y])
continue; fa[y] = x;
pd[i] = pd[i ^ 1] = true;
dep[y] = dep[x] + 1;
dfs(y);
siz[x] += siz[y]; if (siz[y] > mx)
mx = siz[y];
} if (n - siz[x] > mx)
mx = n - siz[x]; if (mx < mn)
mn = mx, rt = x;
}
int imp[N], bl[N], sz[N];
void change(int x, int b) {
bl[x] = b;
sz[b]++; for (re i = head[x]; i; i = nxt[i]) {
int y = to[i]; if (dep[y] != dep[x] + 1)
continue; change(y, b);
}
}
int ji[N], cnt;
int ans[N];
void biao1(int x) {
if (cnt == a[1].first)
return ; ans[x] = a[1].second;
cnt++; for (re i = head[x]; i; i = nxt[i]) {
int y = to[i]; if (y == rt || dep[y] != dep[x] + 1)
continue; biao1(y);
}
}
void biao2(int x, int f) {
if (cnt == a[1].first || ans[x])
return ; ans[x] = a[1].second;
cnt++; for (re i = head[x]; i; i = nxt[i]) {
int y = to[i]; if (bl[y] != f || ans[y])
continue; biao2(y, f);
}
}
void biao3(int x) {
if (cnt == a[2].first)
return ; ans[x] = a[2].second;
cnt++; for (re i = head[x]; i; i = nxt[i]) {
int y = to[i]; if (dep[y] != dep[x] + 1)
continue; biao3(y);
}
}
signed main() {
scanf("%d%d", &n, &m);
scanf("%d%d%d", &a[1].first, &a[2].first, &a[3].first);
a[1].second = 1;
a[2].second = 2;
a[3].second = 3;
sort(a + 1, a + 4); for (re i = 1, x, y; i <= m; i++) {
scanf("%d%d", &x, &y);
x++;
y++;
add_edg(x, y);
add_edg(y, x);
} dfs(1);
siz[0] = n - 1; //cout<<rt<<endl;
for (re i = head[rt]; i; i = nxt[i]) {
int y = to[i]; if (y == fa[rt] || dep[y] != dep[rt] + 1)
continue; change(y, y);
//cout<<rt<<" "<<y<<" "<<siz[0]<<" "<<siz[y]<<endl;
siz[0] -= sz[y];
} //cout<<rt<<" "<<siz[rt]<<" "<<siz[0]<<endl;
for (re i = 2; i <= rp; i += 2) {
if (pd[i])
continue; //cout<<"sb"<<endl;
if (siz[0] >= a[1].first)
break; int u = fr[i], v = to[i]; //cout<<bl[u]<<" "<<bl[v]<<endl;
if (bl[u] && bl[v])
continue; if (!bl[u] && !bl[v])
continue; //cout<<u<<" "<<v<<" "<<siz[bl[u]]<<" "<<siz[bl[v]]<<endl;
if (bl[u] && !ji[bl[u]] && (v != rt || siz[0] == 0)) {
ji[bl[u]] = 1;
imp[bl[u]] = u;
siz[0] += sz[bl[u]];
} if (bl[v] && !ji[bl[v]] && (u != rt || siz[0] == 0)) {
ji[bl[v]] = 1;
imp[bl[v]] = v;
siz[0] += sz[bl[v]];
}
} //cout<<siz[0]<<endl;
int flag = 0; if (siz[0] < a[1].first) {
for (re i = head[rt]; i; i = nxt[i]) {
int y = to[i]; if (dep[y] != dep[rt] + 1)
continue; if (siz[y] >= a[1].first) {
siz[0] = siz[y];
ji[y] = 1;
imp[y] = y;
flag = 1;
break;
}
}
} if (siz[0] >= a[1].first) {
cnt = 0; if ((rt != 1 && !flag))
biao1(1); for (re i = head[rt]; i; i = nxt[i]) {
int y = to[i]; if (!ji[y] || dep[y] != dep[rt] + 1)
continue; if (cnt >= a[1].first)
break; biao2(imp[y], y); //cout<<siz[y]<<endl;
} cnt = 1;
ans[rt] = a[2].second; for (re i = head[rt]; i; i = nxt[i]) {
int y = to[i]; if (ji[y] || dep[y] != dep[rt] + 1)
continue; if (cnt >= a[2].first)
break; biao3(y);
}
} //cout<<a[1].second<<endl;
for (re i = 1; i <= n; i++) {
if (siz[0] >= a[1].first && !ans[i])
ans[i] = a[3].second; printf("%d ", ans[i]);
} //cout<<p<<endl;
}
