#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);
for(auto &k : sub){
if(k.first >= v[0].first && n - k.first >= v[1].first){
found = true;
Colour(k.second, u, 0);
Colour(u, k.second, 1);
return;
}
}
}
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;
}
