#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
const int N = 1e5 + 7;
vector < int > graph[N] , color;
int cur_color = 1;
int dfs1(int node , int sayac){
if(sayac == 0)return node;
// cout << "dfs : " << node << " , " << cur_color << endl;
color[node] = cur_color;
int ret = -1;
for(auto itr : graph[node]){
if(color[itr] == -1){
ret = dfs1(itr , sayac - 1);
break;
}
}
return ret;
}
int subt[N] , tin[N] , tout[N];
vector < int > tour;
int dfs2(int node , int past){
subt[node] = 1;
tour.push_back(node);
tin[node] = sz(tour) - 1;
for(auto itr : graph[node]){
if(subt[itr] == -1){
subt[node] += dfs2(itr , node);
}
}
tout[node] = sz(tour) - 1;
return subt[node];
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
color.assign(n , -1);
for(int i = 0;i<sz(p);i++){
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
bool bl = 1;
for(int i = 0;i<n;i++){
bl &= sz(graph[i]) <= 2;
}
if(bl){
int root = 0;
for(int i = 0;i<n;i++){
if(sz(graph[i]) == 1){
root = i;
break;
}
}
// cout << "root0 : " << root << endl;
root = dfs1(root , a);
cur_color++;
// cout << "root1 : " << root << endl;
root = dfs1(root , b);
cur_color++;
// cout << "root2 : " << root << endl;
root = dfs1(root , c);
}
else{
memset(subt , -1 , sizeof(subt));
dfs2(0 , 0);
int suf[n+1][3];
memset(suf , 0 , sizeof(suf));
for(int i = n-1;i>=0;i--){
suf[i][0] = suf[i+1][0] + (subt[i] == a);
suf[i][1] = suf[i+1][1] + (subt[i] == b);
suf[i][2] = suf[i+1][2] + (subt[i] == c);
}
int query[3] = {a , b, c};
vector < int > perm = {0 , 1 , 2};
// cout << "tour : ";for(auto itr : tour)cout << itr << " ";cout << endl;
do{
// cout << "colors : ";for(auto itr : perm)cout << itr << " ";cout << endl;
int fa = query[perm[0]] , fb = query[perm[1]];
for(int i = 0;i<n;i++){
if(subt[tour[i]] == fa and suf[tout[tour[i]]+1][perm[1]] > 0){
color.assign(n , perm[2] + 1);
// cout << "root for " << perm[0] + 1 << " : " << tour[i] << endl;
for(int j = tin[tour[i]];j<=tout[tour[i]];j++){
color[tour[j]] = perm[0] + 1;
}
int root = -1;
for(int j = tout[tour[i]] + 1;j<n;j++){
if(subt[tour[j]] == fb){
root = tour[j];
break;
}
}
// cout << "root for " << perm[1] + 1 << " : " << root << endl;
for(int j = tin[root];j<=tout[root];j++){
color[tour[j]] = perm[1] + 1;
}
return color;
}
}
} while(next_permutation(all(perm)));
color.assign(n , 0);
}
return color;
}
