#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5;
vector<int> ad[maxn],tr[maxn],cl;
int sz[maxn],s1,s2,n,cnt;
bool vs[maxn];
pair<int,int> pp;
void dfs(int v,int p){
sz[v]=1;
vs[v]=1;
for(int u:ad[v])if(!vs[u]){
tr[u].push_back(v);
tr[v].push_back(u);
dfs(u,v);
sz[v]+=sz[u];
}
if(v!=p&&sz[v]>=s1&&n-sz[v]>=s2)pp={v,p};
}
void dfs2(int v,int p,int c){
if(cnt>0)cl[v]=c;
cnt--;
for(int u:tr[v])if(u!=p)dfs2(u,v,c);
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n=N;
for(int i=0;i<p.size();i++){
ad[p[i]].push_back(q[i]);
ad[q[i]].push_back(p[i]);
}
int ss[]={a,b,c};
for(int i=0;i<3;i++){
for(int j=0;j<3;j++)if(i!=j){
for(int z=0;z<n;z++){
s1=ss[i],s2=ss[j],pp={-1,-1};
memset(vs,0,sizeof(vs));
for(int x=0;x<n;x++)tr[x].clear();
dfs(z,z);
if(pp.first!=-1){
cl=vector<int>(n,4-i-j);
cnt=s1;
dfs2(pp.first,pp.second,i+1);
cnt=s2;
dfs2(pp.second,pp.first,j+1);
return cl;
}
}
}
}
return vector<int>(n,0);
}
