#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
typedef int64_t lld;
typedef pair<int, int> pii;
/*
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<typename T, typename comp = greater<T>>
using OST = tree<T, null_type, comp, rb_tree_tag, tree_order_statistics_node_update>;
*/
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
return out << "(" << p.ff << ", " << p.ss << ")";
}
vector<vector<int>> G;
vector<int> sz;
int dfs(int i, int p, int n){
bool fl = true; int s = 1;
for(auto x: G[i])
if(x != p){
int a = dfs(x, i, n);
if(a >= 0)return a;
if(-a > n/2)fl = false;
s += -a;
}
if(n-s > n/2)fl = false;
if(fl)return i;
return -s;
}
void dfs1(int i, int p){
for(auto x: G[i])
if(x != p) dfs1(x, i), sz[i] += sz[x];
}
vector<int> ans;
int dfspaint(int i, int p, int cnt, int col){
if(!cnt)return 0;
ans[i] = col; cnt--;
for(auto x: G[i])
if(x != p)cnt = dfspaint(x, i, cnt, col);
return cnt;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<pii> cuts = {{a, 1}, {b, 2}, {c, 3}};
sort(all(cuts));
G.resize(n); sz.resize(n, 1); ans.resize(n);
for(int i = 0; i < p.size(); i++)
G[p[i]].pb(q[i]), G[q[i]].pb(p[i]);
if(q.size() == n-1){
int root = dfs(0, 0, n);
dfs1(root, root);
pii maxs = {-1, -1};
for(auto x: G[root])maxs = max(maxs, (pii){sz[x], x});
if(cuts[0].ff > maxs.ff)return ans;
assert(!dfspaint(maxs.ss, root, cuts[0].ff, cuts[0].ss));
assert(!dfspaint(root, maxs.ss, cuts[1].ff, cuts[1].ss));
for(auto& i: ans)if(!i)i = cuts[2].ss;
return ans;
}
return ans;
}
