#include "split.h"
#include <bits/stdc++.h>
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define here cerr<<"============================================\n"
#define ll long long
#define llinf 1000000000000LL
#define sz(a) (ll)(a.size())
#define pb push_back
#define all(a) a.begin(),a.end()
#define popb pop_back
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 100005
ll n,m;
vector<ll> g[maxn];
ll x,y,z;
ll col[maxn];
ll siz[maxn],sizmx[maxn],par[maxn];
void dfs1(ll u){
if(!y) return;
col[u] = 2;
y--;
for(ll s : g[u]) if(!col[s]) dfs1(s);
}
void dfs2(ll u){
if(x) col[u] = 1,x--;
else if(y) col[u] = 2,y--;
else col[u] = 3,z--;
for(ll s : g[u]) if(!col[s]) dfs2(s);
}
ll nod = -1; bool f;
ll dfssiz(ll u,ll p){
siz[u] = 1;
par[u] = p;
for(ll s : g[u]){
if(s!=p){
dfssiz(s,u);
siz[u]+=siz[s];
sizmx[u] = max(sizmx[s],sizmx[u]);
}
}
if(nod==-1){
if(siz[u]>=x&&n-siz[u]>=y){
nod = u; f = 1;
}else if(siz[u]>=y&&n-siz[u]>=x){
nod = u; f = 0;
}
}
return siz[u];
}
void dfscol(ll u,ll w){
if(!col[u]){
if((f==1)&&(x>0)){
col[u] = 1;
x--;
}
else if((f==0)&&(y>0)){
col[u] = 2; y--;
}
else col[u] = 3;
}
for(ll s : g[u]){
if(s==w) continue;
if(col[s]) continue;
dfscol(s,w);
}
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
n = N;
m = sz(p);
x = A,y = B,z = C;
for(ll i = 0;i<m;i++){
ll x = p[i],y = q[i];
x++; y++;
g[x].pb(y);
g[y].pb(x);
}
ll mxdeg = 0,mndeg = llinf;
for(ll i = 1;i<=n;i++) mxdeg = max(mxdeg,sz(g[i]));
for(ll i = 1;i<=n;i++) mndeg = min(mndeg,sz(g[i]));
if(mxdeg<=2){
ll poc = 1;
if(mndeg==1){
for(ll i = 1;i<=n;i++) if(sz(g[i])==1) poc = i;
}
dfs2(poc);
vector<int> ans(n);
for(ll i = 1;i<=n;i++) ans[i-1] = col[i];
return ans;
}
if(x==1){
dfs1(1);
for(ll i = 1;i<=n;i++){
if(col[i]) continue;
if(x){
col[i] = 1;
x--;
}else col[i] = 3;
}
vector<int> ans(n);
for(ll i = 1;i<=n;i++) ans[i-1] = col[i];
return ans;
}
if(m==n-1){
vector<ll> w = {A,B,C}; sort(all(w)); x = w[0],y = w[1],z = w[2];
dfssiz(1,1);
vector<int> ans(n);
if(nod==-1) return ans;
for(ll i = 1;i<=n;i++) col[i] = 0;
dfscol(nod,par[nod]);
f^=1;
dfscol(nod,0);
vector<ll> cur(4);
for(ll i = 1;i<=n;i++) if(!col[i]) col[i] = 3;
for(ll i = 1;i<=n;i++) cur[col[i]]++;
for(ll i = 1;i<=n;i++) ans[i-1] = col[i];
return ans;
}
return {};
}
