#include "split.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int sz[100010];
vector<int> adj[100010];
vector<pair<int, int> > v;
bool found = false;
vector<int> res;
void Colour(int u, int p, int id){
if(v[id].first == 0) return;
res[u] = v[id].second;
v[id].first--;
for(auto &v : adj[u]){
if(v == p) continue;
Colour(v, u, id);
}
}
void dfs(int u, int p) {
sz[u] = 1;
vector<pair<int, int> > sub;
for(auto &v : adj[u]){
if(v == p) continue;
dfs(v, u);
if(found) return;
sz[u] += sz[v];
sub.emplace_back(sz[v], v);
}
sub.emplace_back(n - sz[u], p);
sort(sub.begin(), sub.end());
int id = 0, sk[2];
bool used = false;
for(auto &k : sub){
if(k.first >= v[id].first || (id == 0 && k.first + 1 >= v[id].first)){
if(k.first >= v[id].first);
else used = true;
sk[id++] = k.second;
}
}
if(id == 2) {
found = true;
Colour(sk[0], u, 0);
Colour(sk[1], u, 1);
if(used) res[u] = v[0].second;
} else {
id = 0;
used = false;
for(auto &k : sub){
if(k.first >= v[id].first || (id == 1 && k.first + 1 >= v[id].first)){
if(k.first >= v[id].first);
else used = true;
sk[id++] = k.second;
}
}
if(id == 2) {
found = true;
Colour(sk[0], u, 0);
Colour(sk[1], u, 1);
if(used) res[u] = v[1].second;
}
}
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
n = _n;
v.emplace_back(a, 1);
v.emplace_back(b, 2);
v.emplace_back(c, 3);
sort(v.begin(), v.end());
for(int i = 0; i < (int) p.size(); i++){
adj[p[i]].emplace_back(q[i]);
adj[q[i]].emplace_back(p[i]);
}
res.assign(n, 0);
dfs(0, -1);
if(found) for(auto &k : res) if(k == 0) k = v[2].second;
return res;
}
