#include "split.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
vector<int>adj[100005];
int N, m;
bool vis[100005];
int abajo[100005], maximo[100005];
int dfs(int u){
vis[u] = true;
abajo[u] = 0;
maximo[u] = 0;
int cu = 0;
for(int i = 0 ; i < adj[u].size() ; i ++){
if(vis[adj[u][i]]){
continue;
}
cu = dfs(adj[u][i]);
abajo[u] += cu;
maximo[u] = max(maximo[u], cu);
}
return abajo[u] + 1;
}
vector<int> respuesta;
int A, B;
int mejor, donde;
void dp(int u){
vis[u] = true;
if(A - (abajo[u] + 1) <= 0 and (abajo[u] + 1 < mejor)){
mejor = abajo[u] + 1;
donde = u;
//cout << "new best " << u << endl;
}
for(int i = 0 ; i < adj[u].size() ; i ++){
if(vis[adj[u][i]])continue;
dp(adj[u][i]);
}
}
void generarSubArbol(int u, int val, int &restantes){
//cout << "generando " << u << " val " << val << " res " << restantes << endl;
if(restantes <= 0){
return ;
}
vis [ u ] = true;
respuesta[u] = val;
restantes --;
if(restantes <= 0)return ;
for(int i = 0 ; i < adj[u].size() ; i ++){
if(vis[adj[u][i]])continue;
generarSubArbol(adj[u][i], val, restantes);
if(restantes <= 0)return ;
}
}
int bfs(int st){
queue<int>cola;
memset(vis, false, sizeof vis);
cola.push(st);
int distancia[N+3];
vis[st] = true;
distancia[st] = 0;
while(!cola.empty()){
int cur = cola.front();
cola.pop();
for(int i = 0 ; i < adj[cur].size() ; i ++){
if(vis[adj[cur][i]])continue;
cola.push(adj[cur][i]);
vis[adj[cur][i]] = true;
distancia[adj[cur][i]] = distancia[cur] + 1;
}
}
int hoja, dist = 0;
for(int i = 0 ; i < N ; i ++){
if(distancia[i] > dist)hoja = i, dist = distancia[i];
}
return hoja;
}
vector<int> test(int root, int a, int b, int c){
int n = N;
vector<int>all0;
for(int i = 0 ; i < n ; i ++)all0.pb(0);
memset(vis, false, sizeof vis);
dfs(root);
//for(int i = 0 ; i < n ; i ++)cout << abajo[i] << endl;
//cout << endl;
vector<int> opt;
opt.pb(a);
opt.pb(b);
opt.pb(c);
sort(opt.begin(), opt.end());
A = opt[0];
B = opt[1];
mejor = INT_MAX;
donde = root;
respuesta.clear();
for(int i = 0 ; i < n ; i++)respuesta.pb(0);
memset(vis, false, sizeof vis);
dp(root);
if(donde == root)return all0;
int restantes = A - 1;
memset(vis, false, sizeof vis);
vis[donde] = true;
int parent = root;
for(auto i : adj[donde]){
if(abajo[i] > abajo[donde]){
continue;
}
generarSubArbol(i, 1, restantes);
if(restantes <= 0 )break;
}
respuesta[donde] = 1;
restantes = B;
//cout << "donde " << donde << " parent " << parent << endl;
generarSubArbol(parent, 2, restantes);
if(restantes > 0)return all0;
for(int i = 0 ; i < n ; i ++)if(respuesta[i] == 0)respuesta[i] = 3;
int mapeo[4];
bool banned[3];
memset(banned, false, sizeof banned);
for(int i = 0 ; i < 3 ; i ++){
if(opt[i] == a and !banned[0]){
banned[0] = true;
mapeo[i+1] = 1;
}else if(opt[i] == b and !banned[1]){
banned[1] = true;
mapeo[i+1] = 2;
}else{
banned[2] = true;
mapeo[i+1] = 3;
}
}
for(int i = 0 ; i < n ; i++){
respuesta[i] = mapeo[respuesta[i]];
}
return respuesta;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n;
m = p.size();
for(int i = 0 ; i < m ; i ++){
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
int rootA = bfs(0), rootB = rootA;
vector<int>respA = test(rootA, a, b, c);
if(respA[0] != 0){
return respA;
}else return test(rootB, a, b, c);
}
