#include <bits/stdc++.h>
#include "split.h"
using namespace std;
const int MAXN = 1e5 + 10;
vector<int> split, ord;
set<int> marc[MAXN];
int pre[MAXN], pos[MAXN], id[MAXN], sub[MAXN];
vector<int> adj[MAXN];
vector<int> ans;
pair<int, int> first_split, second_split;
int n, t = 0;
void dfs_1(int v, int p){
sub[v] = 1;
pre[v] = ++t;
id[pre[v]] = v;
for(auto u : adj[v]){
if(u != p){
dfs_1(u, v);
sub[v] += sub[u];
}
}
for(auto u : adj[v]){
if(u != p){
if(n - sub[v] == split[0] && sub[u] == split[1]) first_split = {v, u};
}
}
pos[v] = t;
}
void dfs_2(int v, int p){
marc[sub[v]].erase(pre[v]);
if(sub[v] == split[0] && !marc[split[1]].empty()){
int cand_l = *marc[split[1]].begin(), cand_r = *marc[split[1]].rbegin();
if(cand_l < pre[v]){
second_split = {v, id[cand_l]};
} else if(cand_r > pre[v]) second_split = {v, id[cand_r]};
}
for(auto u : adj[v]){
if(u != p){
dfs_2(u, v);
}
}
marc[sub[v]].insert(pre[v]);
}
bool is_sub(int a, int b){
return pre[b] <= pre[a] && pos[a] <= pos[b];
}
bool check(){
dfs_1(0, 0);
if(first_split.first != -1){
auto [v, u] = first_split;
for(int i=0; i<n; i++){
if(is_sub(i, u)){
ans[i] = ord[1];
} else if(is_sub(i, v)){
ans[i] = ord[2];
} else ans[i] = ord[0];
}
return true;
}
for(int i=0; i<n; i++) marc[sub[i]].insert(pre[i]);
dfs_2(0, 0);
if(second_split.first != -1){
auto [v, u] = second_split;
for(int i=0; i<n; i++){
if(is_sub(i, v)){
ans[i] = ord[0];
} else if(is_sub(i, u)){
ans[i] = ord[1];
} else ans[i] = ord[2];
}
return true;
}
return false;
}
vector<int> find_split(int n_, int a, int b, int c, vector<int> p, vector<int> q){
n = n_;
ans.resize(n);
first_split = second_split = {-1, -1};
split = {a, b, c};
ord = {1, 2, 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;
do{
ok |= check();
} while(!ok && (next_permutation(split.begin(), split.end()) && next_permutation(ord.begin(), ord.end())));
return ans;
}
