#include "split.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
vector<int>adj[100005];
int par[100005], sum[100005], ans[100005];
pii A, B;
bool done=false;
int cnter, bad, n;
void go(int x, int p, int v){
if(cnter && !ans[x]){
cnter--;
ans[x]=v;
}
for(int y:adj[x]){
if(y==p) continue;
go(y, x, v);
}
}
void dfs(int x, int p){
par[x]=p;
sum[x]=1;
vector<pair<int, int>>cur;
for(int y:adj[x]){
if(y==p) continue;
dfs(y, x);
sum[x]+=sum[y];
cur.push_back({sum[y], y});
}
cur.push_back({n-sum[x], 0});
sort(cur.rbegin(), cur.rend());
if(cur.size()==1) return;
if(cur[0].first >= B.first && cur[1].first >= A.first && !done){
/*cout<<x<<" "<<cur.size()<<endl;
for(auto [x, y]:cur){
cout<<x<<" "<<y<<endl;
}*/
done=true;
cnter=B.first;
if(cur[0].second!=0) go(cur[0].second, par[cur[0].second], B.second);
cnter=A.first;
go(cur[1].second, par[cur[1].second], A.second);
cnter=B.first;
if(cur[0].second==0) go(cur[0].second, par[cur[0].second], B.second);
for(int i=0;i<n;i++){
if(!ans[i]) ans[i]=bad;
}
}
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
n=_n;
assert((int) p.size()==n-1);
for(int i=0;i<p.size();i++){
int x=p[i], y=q[i];
adj[x].push_back(y);
adj[y].push_back(x);
}
vector<pii>v={{a, 1}, {b, 2}, {c, 3}};
sort(v.begin(), v.end());
A=v[0], B=v[1], bad=v[2].second;
dfs(0, -1);
vector<int>fans;
for(int i=0;i<n;i++){
fans.push_back(ans[i]);
}
return fans;
}
