#include "split.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
const int maxN=1e5+5;
vector<int> ans(maxN),g[maxN];
int used[maxN];
vector<pair<int,int>> e;
int n;
void dfs(int x){
used[x]=1;
for(auto it: g[x]){
if(!used[it]){
dfs(it);
e.push_back({x,it});
}
}
}
int sz[maxN];
int u=-1,v=-1,a,b,c;
void dfs1(int x, int p){
sz[x]=1;
for(auto it: g[x]){
if(it==p) continue;
dfs1(it,x);
sz[x]+=sz[it];
}
if(min(sz[x],n-sz[x])>=a){
u=x,v=p;
}
}
void dfs2(int x, int p, int c){
ans[x]=c;
for(auto it: g[x]){
if(it==p) continue;
dfs2(it,x,c);
}
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
int A=1,B=2,C=3,m=p.size();
a=_a,b=_b,c=_c;
n=_n;
if(a>b){
swap(a,b);
swap(A,B);
}
if(b>c){
swap(b,c);
swap(B,C);
}
if(a>b){
swap(a,b);
swap(A,B);
}
for(int i=0;i<m;i++){
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
dfs(0);
for(int i=0;i<n;i++){
g[i].clear();
}
for(auto c: e){
g[c.fr].push_back(c.sc);
g[c.sc].push_back(c.fr);
}
dfs1(0,0);
vector<int> res(n,0);
if(v==-1) return res;
res=vector<int> (n,C);
if(sz[u]>=b) swap(u,v);
dfs2(u,v,A);
dfs2(v,u,B);
for(int i=0;i<n;i++)
if(ans[i]) res[i]=ans[i];
return res;
}
