#include "split.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
struct UnionFind{
vector<int>par;
UnionFind(int n){par=vector<int>(n);rep(i,n)par[i]=i;}
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
void unite(int x,int y){
x=find(x);y=find(y);
par[y]=x;
}
bool same(int x,int y){
return find(x)==find(y);
}
};
static vector<int>E[200000];
static int sz[200000],par[200000];
static vector<int>col;
static int cnt1=0,cnt2=0;
void dfs(int v,int p){
sz[v]=1;
par[v]=p;
for(int u:E[v]){
if(u==p)continue;
dfs(u,v);
sz[v]+=sz[u];
}
}
void dfs2(int v,int p,int c){
if(cnt1==0)return;
col[v]=c;
cnt1--;
for(int u:E[v]){
if(u==p)continue;
dfs2(u,v,c);
}
}
void dfs3(int v,int p,int c){
if(cnt2==0)return;
col[v]=c;
cnt2--;
for(int u:E[v]){
if(u==p||col[u]!=0)continue;
dfs3(u,v,c);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m=p.size();
col=vector<int>(n);
UnionFind uf(n);
rep(i,m){
if(uf.same(p[i],q[i]))continue;
E[p[i]].push_back(q[i]);
E[q[i]].push_back(p[i]);
uf.unite(p[i],q[i]);
}
vector<P>v{P(a,1),P(b,2),P(c,3)};
sort(v.begin(),v.end());
dfs(0,-1);
rep(i,n){
if(sz[i]>=v[0].first&&n-sz[i]>=v[1].first){
cnt1=v[0].first;
dfs2(i,par[i],v[0].second);
cnt2=v[1].first;
dfs3(0,-1,v[1].second);
rep(i,n){
if(col[i]==0)col[i]=v[2].second;
}
return col;
}
if(sz[i]>=v[1].first&&n-sz[i]>=v[0].first){
cnt1=v[1].first;
dfs2(i,par[i],v[1].second);
cnt2=v[0].first;
dfs3(0,-1,v[0].second);
rep(i,n){
if(col[i]==0)col[i]=v[2].second;
}
return col;
}
}
return col;
}
