#include "split.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int>v[maxn], filhos[maxn];
int marc[maxn], sub[maxn], pai[maxn], cor[maxn], prof[maxn], ja[maxn], n, in[maxn], low[maxn], tmp;
bool sair;
pair<int,int>z[3];
int calc(int u, int x, int c, int lim){
ja[u]++;
if(x){
//cout << "! " << x << " " << u << ' ' << c << endl;
cor[u]=c;
x--;
}
for(int viz : v[u]){
if(ja[viz]||prof[viz]<lim) continue;
x=calc(viz,x,c,lim);
}
return x;
}
int termina(int u, int x, int c){
ja[u]++;
if(x){
//cout << "! " << x << " " << cor[u] << " " << u << " " << c << endl;
cor[u]=c;
x--;
}
for(int viz : v[u]){
if(ja[viz]||cor[viz]) continue;
x=termina(viz,x,c);
}
return x;
}
void dfs(int u){
marc[u]++;
sub[u]=1;
in[u]=low[u]=++tmp;
int ma=0;
for(int viz : v[u]){
if(pai[u]==viz) continue;
if(marc[viz]){
low[u]=min(low[u],in[viz]);
continue;
}
filhos[u].push_back(viz);
pai[viz]=u;
prof[viz]=prof[u]+1;
dfs(viz);
if(sair) return;
low[u]=min(low[u],in[viz]);
ma=max(ma,sub[viz]);
sub[u]+=sub[viz];
}
if(sub[u]>=z[0].first&&ma<z[0].first){ // achei o cara com a propriedade
cout << "get " << u << " " << pai[u] << endl;
int x=sub[u], y=n-sub[u];
vector<int>aux;
for(int viz : filhos[u]){
if(in[viz]<in[u]||low[viz]>in[u]||z[0].first<=y) continue;
// ou seja tem backedge para cima
aux.push_back(viz);
x-=sub[viz];
y+=sub[viz];
}
if(z[0].first<=y){ // deu bom
if(z[1].first>y) swap(z[0],z[1]);
for(int viz : aux) z[1].first=calc(viz,z[1].first,z[1].second,prof[viz]);
for(int viz : v[u]) if(!ja[viz]&&viz!=pai[u]) z[0].first=calc(viz,z[0].first,z[0].second,prof[viz]);
if(z[0].first){
cor[u]=z[0].second;
z[0].first--;
}
z[1].first=termina(pai[u],z[1].first,z[1].second);
}
sair=true;
return;
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q){
n=N;
for(int i=0;i<p.size();i++){
v[p[i]].push_back(q[i]);
v[q[i]].push_back(p[i]);
}
z[0]={a,1}; z[1]={b,2}; z[2]={c,3};
sort(z,z+3);
sair=false;
dfs(0);
vector<int>resp(n,0);
for(int i=0;i<n;i++){
//cout << cor[i] << ' ';
if(z[0].first+z[1].first) resp[i]=0;
else if(cor[i]) resp[i]=cor[i];
else resp[i]=z[2].second;
}
//cout << endl;
return resp;
}
