#include <bits/stdc++.h>
#include "split.h"
using namespace std;
const int MAXN = 2e5 + 10;
vector<pair<int, int>> split;
int pre[MAXN], pos[MAXN];
int sub[MAXN], pai[MAXN];
vector<int> adj[MAXN];
vector<int> ans;
int n, t = 0;
void dfs_1(int v, int p){
sub[v] = 1;
for(auto u : adj[v]){
if(u != p){
pai[u] = v;
dfs_1(u, v);
sub[v] += sub[u];
}
}
}
void dfs_2(int v, int p){
pre[v] = ++t;
for(auto u : adj[v]){
if(u != p){
dfs_2(u, v);
}
}
pos[v] = t;
}
bool is_sub(int a, int b){
return pre[b] <= pre[a] && pos[a] <= pos[b];
}
bool check(){
int root = -1, v = -1, u = -1;
for(int i=0; i<n; i++){
int cur_v = -1, cur_u = -1;
for(auto j : adj[i]){
if(j != pai[i]){
if(cur_v == -1 && sub[j] == split[0].first){
cur_v = j;
} else if(cur_u == -1 && sub[j] == split[1].first) cur_u = j;
} else{
if(cur_v == -1 && n - sub[i] == split[0].first){
cur_v = j;
} else if(cur_u == -1 && n - sub[i] == split[1].first) cur_u = j;
}
}
if(cur_v != -1 && cur_u != -1){
v = cur_v; u = cur_u;
root = i;
break;
}
}
if(root == -1) return false;
t = 0;
dfs_2(root, root);
for(int i=0; i<n; i++){
if(is_sub(i, v)){
ans[i] = split[0].second;
} else if(is_sub(i, u)){
ans[i] = split[1].second;
} else ans[i] = split[2].second;
}
return true;
}
vector<int> find_split(int n_, int a, int b, int c, vector<int> p, vector<int> q){
n = n_;
ans.resize(n);
for(int i=0; i<n; i++) ans[i] = 0;
split = {{a, 1}, {b, 2}, {c, 3}};
for(int i=0; i<(n - 1); i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
sort(split.begin(), split.end());
bool ok = false;
dfs_1(0, 0);
do{
ok |= check();
} while(!ok && next_permutation(split.begin(), split.end()));
return ans;
}
