#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;
int dp(int u){
vis[u] = true;
int minimo = INT_MAX;
if(A - (abajo[u] + 1) <= 0 and (abajo[u] + 1 < mejor)){
mejor = abajo[u] + 1;
donde = u;
minimo = abajo[u] + 1;
//cout << "new best " << u << endl;
}
for(int i = 0 ; i < adj[u].size() ; i ++){
if(vis[adj[u][i]])continue;
minimo = min ( minimo, dp(adj[u][i]));
}
if(A - (abajo[u] + 1) > 0)return minimo;
else return min ( minimo, (abajo[u] + 1) );
}
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 --;
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 ;
}
}
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]);
}
memset(vis, false, sizeof vis);
dfs(0);
//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];
c = opt[2];
A = a;
B = b;
mejor = INT_MAX;
for(int i = 0 ; i < n ; i++)respuesta.pb(0);
memset(vis, false, sizeof vis);
if(dp(0) == INT_MAX){
return respuesta;
}
int restantes = A - 1;
memset(vis, false, sizeof vis);
vis[donde] = true;
int parent = 0;
for(auto i : adj[donde]){
if(abajo[i] > abajo[donde]){
parent = i;
continue;
}
generarSubArbol(i, 1, restantes);
if(restantes <= 0 )break;
}
respuesta[donde] = 1;
restantes = B;
//cout << "donde " << donde << " parent " << parent << endl;
generarSubArbol(parent, 2, restantes);
for(int i = 0 ; i < n ; i ++)if(respuesta[i] == 0)respuesta[i] = 3;
return respuesta;
}
