#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define sz(x) ((int)(x).size())
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=100000+10;
const int M=200000+10;
const double eps=1e-5;
const int mo=1e9+7;
int n,m,A,B,C,a,b,c;
int head[N];
int nxt[2*M];
int to[2*M];
int cnt;
int dfn[N],nn;
int f[N];
int num[N];
int sz[N];
int s[N],tail;
bool colored[N];
bool found=0;
bool vis[N];
int remain;
int colors[4];
int ans[N];
void color(int x,int fa) {
colored[x]=1;
int y;
for (int i=head[x];i;i=nxt[i]) {
y=to[i];
if (y!=fa&&dfn[y]>dfn[x]) {
color(y,x);
}
}
}
void add(int x,int y) {
nxt[++cnt]=head[x];
to[cnt]=y;
head[x]=cnt;
nxt[++cnt]=head[y];
to[cnt]=x;
head[y]=cnt;
}
void dfs(int x,int fa) {
int y;
sz[x]=1;
dfn[x]=++nn;
f[x]=nn;
for (int i=head[x];i;i=nxt[i]) {
y=to[i];
if (y!=fa) {
if (!dfn[y]) {
dfs(y,x);
sz[x]+=sz[y];
num[x]++;
f[x]=min(f[x],f[y]);
} else f[x]=min(f[x],dfn[y]);
}
}
}
void solve(int x,int fa) {
int y;
int maxsz=0,p=0,p2=0,cntb=0,sum=0;
for (int i=head[x];i;i=nxt[i]) {
y=to[i];
if (y!=fa&&dfn[y]>dfn[x]) {
if (sz[y]>=b) {
if (!p) p=y;
else p2=y;
cntb++;
}
}
}
if (cntb>=2) {
color(p,x);
found=1;
} else if (cntb==1) {
if (n-sz[p]>=c) {
color(p,x);
found=1;
} else {
solve(p,x);
}
} else {
tail=0;
sum=n-sz[x];
for (int i=head[x];i;i=nxt[i]) {
y=to[i];
if (y!=fa&&dfn[y]>dfn[x]) {
if (f[y]<dfn[x]) {
// 有前向边连接上树
s[++tail]=y;
sum+=sz[y];
if (sum>=c) {
// find
// 注意find处理完后要退出循环
for (int j=head[x];j;j=nxt[j]) {
y=to[j];
if (y!=fa&&dfn[y]>dfn[x]) {
if (f[y]>=dfn[x]) {
color(y,x);
}
}
}
colored[x]=1;
found=1;
break;
}
}
}
}
if (found) return;
for (int i=head[x];i;i=nxt[i]) {
y=to[i];
if (y!=fa&&dfn[y]>dfn[x]) {
if (f[y]>=dfn[x]&&sz[y]>=c) {
// find
color(y,x);
found=1;
break;
}
}
}
if (found) return;
for (int i=head[x];i;i=nxt[i]) {
y=to[i];
if (y!=fa&&dfn[y]>dfn[x]) {
if (f[y]<dfn[x]&&sz[y]>=c) {
// find
color(y,x);
found=1;
break;
}
}
}
// 无解
}
}
void grow(int x) {
if (remain==0) {
return;
}
vis[x]=1;
remain--;
if (remain==0) {
return;
}
int y;
for (int i=head[x];i;i=nxt[i]) {
y=to[i];
if (!vis[y]&&colored[y]==colored[x]) {
grow(y);
}
}
}
vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) {
n=N,m=int(P.size()),a=A,b=B,c=C;
REP(i,0,2) colors[i]=i+1;
a=A,b=B,c=C;
vector<int> res;
if (c>a) {
swap(c,a);
swap(colors[2],colors[0]);
}
if (c>b){
swap(c,b);
swap(colors[2],colors[1]);
}
if (b>a) {
swap(a,b);
swap(colors[0],colors[1]);
}
for (int i=0;i<m;i++) add(P[i]+1,Q[i]+1);
if (c>a) {
swap(c,a);
swap(colors[2],colors[0]);
}
if (c>b){
swap(c,b);
swap(colors[2],colors[1]);
}
if (b>a) {
swap(a,b);
swap(colors[0],colors[1]);
}
int maxsz=0,p=0,root=1;
dfs(root,0);
int y;
for (int i=head[root];i;i=nxt[i]) {
y=to[i];
//if (y!=fa) {
// 树根没有fa
if (maxsz<sz[y]) {
maxsz=sz[y];
p=y;
}
//}
}
if (c<=maxsz&&maxsz<=a) {
color(p,root);
found=1;
} else if (maxsz<c) {
// 无解
} else if (maxsz>a) {
if (sz[root]-maxsz>=c) {
color(p,root);
found=1;
} else if (sz[root]-maxsz<c) {
solve(p,root);
}
}
if (found) {
int s=0;
FOR(i,n) if (colored[i]) s++;
if (n-s>=s) {
FOR(i,n) if (colored[i]) {
remain=c;
grow(i);
FOR(j,n) if (vis[j]) ans[j]=colors[2];
memset(vis,0,sizeof(vis));
break;
}
FOR(i,n) if (!colored[i]) {
remain=b;
grow(i);
FOR(j,n) if (vis[j]) ans[j]=colors[1];
memset(vis,0,sizeof(vis));
break;
}
FOR(j,n) if (!ans[j]) ans[j]=colors[0];
} else {
FOR(i,n) if (colored[i]) {
remain=b;
grow(i);
FOR(j,n) if (vis[j]) ans[j]=colors[1];
memset(vis,0,sizeof(vis));
break;
}
FOR(i,n) if (!colored[i]) {
remain=c;
grow(i);
FOR(j,n) if (vis[j]) ans[j]=colors[2];
memset(vis,0,sizeof(vis));
break;
}
FOR(j,n) if (!ans[j]) ans[j]=colors[0];
}
FOR(i,n) ans[i]--;
//FOR(i,n) cout<<ans[i]<<" ";
FOR(i,n) res.pb(ans[i]);
} else {
FOR(i,n) res.pb(0);
}
return res;
}
/*
int main() {
int n, m, a, b, c;
assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
vector<int> p(m), q(m);
for (int i=0; i<m; i++)
assert(2 == scanf("%d%d", &p[i], &q[i]));
fclose(stdin);
vector<int> result = find_split(n, a, b, c, p, q);
for (int i=0; i<(int)result.size(); i++)
printf("%s%d", ((i>0)?" ":""), result[i]);
printf("\n");
fclose(stdout);
return 0;
}*/
