#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define debug(v) cerr << #v << ": " << v << " ";
#define debugln(v) cerr << #v << ": " << v << endl;
const int MAXN = 1e5+5;
int small, large, meio;
vector<int> res, imp;
vector<int> adj[MAXN];
int pai[MAXN], sz[MAXN];
bool used1[MAXN], used2[MAXN], used3[MAXN];
void dfs_1(int no){
used1[no] = true;
sz[no] = 1;
for(int v : adj[no]){
if(used1[v]) continue;
pai[v] = no;
dfs_1(v);
sz[no] += sz[v];
}
}
void dfs_2(int no, int c){
used2[no] = true;
// debug(small) debugln(no);
res[no] = c;
for(int v : adj[no]){
if(used2[v] || small == 0) continue;
small--;
dfs_2(v, c);
}
}
void dfs_3(int no, int c){
used3[no] = true;
// debug(meio) debugln(no);
res[no] = c;
for(int v : adj[no]){
if(used3[v] || meio == 0) continue;
meio--;
dfs_3(v, c);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
res.resize(n);
imp.resize(n, 0);
small = min({a, b, c});
large = max({a, b, c}); //vai ser galera soltos
meio = n-small-large; //vai ser o que der
for(int i = 0; i < (int)p.size(); i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
dfs_1(0);
// cerr << "i sz pai\n";
vector<pair<int, int>> aux;
for(int i = 0; i < n; i++){
// cerr << i << " " << sz[i] << " " << pai[i] << "\n";
aux.push_back({sz[i], i});
}
sort(aux.begin(), aux.end());
int sm = lower_bound(aux.begin(), aux.end(), make_pair(small, 0))->second;
int can2 = lower_bound(aux.begin(), aux.end(), make_pair(meio, 0))->second;
if(sz[sm]-small > sz[can2]-meio) sm = can2;
if(n-sz[sm] < meio) return imp;
// debugln(sm);
// debugln(pai[sm]);
int cor3 = 6;
used2[pai[sm]] = true;
small--;
if(small+1 == a){
dfs_2(sm, 1);
cor3--;
a = 0;
}
else if(small+1 == b){
dfs_2(sm, 2);
cor3-=2;
b = 0;
}
else{
dfs_2(sm, 3);
cor3-=3;
c = 0;
}
// debugln(cor3);
used3[sm] = true;
meio--;
if(a != 0 && meio+1 == a){
dfs_3(pai[sm], 1);
cor3--;
}
else if(b != 0 && meio+1 == b){
dfs_3(pai[sm], 2);
cor3-=2;
}
else{
dfs_3(pai[sm], 3);
cor3-=3;
}
// debugln(cor3);
for(int &i : res) if(i == 0) i = cor3;
return res;
}
