#include<bits/stdc++.h>
#include "split.h"
using namespace std;
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
const int MX=1e5+7;
vector<pair<int,int>> adj[MX];//onde vai e tipo
int tam[MX];
int n;
int dfstam(int node){
tam[node]=1;
L(i,0,sz(adj[node])-1){
if(tam[adj[node][i].first]==0){
adj[node][i].second=1;;
tam[node]+=dfstam(adj[node][i].first);
}
}
return tam[node];
}
int cen(int node){
for(auto [a,w]:adj[node]){
if(w==0)continue;
if(tam[a]*2>n)return cen(a);
}
return node;
}
int rep[MX];
void findrep(int node,int pai,int r){
rep[node]=r;
for(auto [a,w]:adj[node]){
if(w==0 || a==pai)continue;
findrep(a,node,r);
}
}
int c;
vector<int> ultradj[MX];
vector<int> resp;
void superliga(int node, int pai){
for(auto [a,w]:adj[node]){
if(a==pai)continue;
if(w==0 && a!=c){
if(rep[node]==rep[a])continue;
ultradj[rep[node]].push_back(rep[a]);
ultradj[rep[a]].push_back(rep[node]);
}
if(w==1){
superliga(a,node);
}
}
}
void pintasub(int node, int pai,int cor){
resp[node]=cor;
for(auto [a,w]:adj[node]){
if(w==0 || a==pai)continue;
pintasub(a,node,cor);
}
return;
}
void pintoQnt(int node, int pai, int cor, int qnt){
resp[node]=cor;
qnt--;
if(qnt<=0)return;
for(auto [a,w]:adj[node]){
if(w==0 || a==pai)continue;
pintoQnt(a,node,cor,qnt);
qnt-=tam[a];
if(qnt<=0)return;
}
return;
}
int ultratam[MX];
int ultradfs(int node, int pai){
ultratam[node]=tam[node];
for(auto a:ultradj[node]){
if(ultratam[a]==0)ultratam[node]+=ultradfs(a,node);
}
return ultratam[node];
}
void ultramarca(int node,int cor, int& qnt){
if(qnt==0)return;
if(tam[node]<=qnt){
qnt-=tam[node];
pintasub(node,c,cor);
}
else{
pintoQnt(node,c,cor,qnt);
qnt=0;
}
if(qnt==0)return;
for(auto a:ultradj[node]){
if(resp[a]!=0)continue;
ultramarca(a,cor,qnt);
}
}
vector<int> find_split(int nn, int aa, int bb, int cc, vector<int> p, vector<int> q) {
n=nn;
resp.resize(n);
L(i,0,sz(p)-1){
adj[p[i]].push_back({q[i],0});
adj[q[i]].push_back({p[i],0});
}
dfstam(0);
c=cen(0);
for(auto [a,w]:adj[c]){
if(w==0)continue;
findrep(a,c,a);
}
vector<int> cor(3);iota(all(cor),1);
int preciso[3]={aa,bb,cc};
sort(all(cor),[&](int i, int j){
return preciso[i-1]<preciso[j-1];
});
sort(preciso,preciso+3);//ver se eh +2
for(auto [a,w]:adj[c]){
if(w==0)continue;
superliga(a,c);
}
for(auto [a,w]:adj[c]){
if(w==0)continue;
if(sz(ultradj[a])==0)continue;
sort(all(ultradj[a]));
ultradj[a].erase(unique(all(ultradj[a])),ultradj[a].end());
}
vector<int> vizc;
for(auto [a,w]:adj[c]){
if(w==0)continue;
vizc.push_back(a);
}
for(auto a:vizc){
if(ultratam[a]!=0)continue;
ultradfs(a,c);
if(ultratam[a]>=preciso[0]){//yayyy deu certo
ultramarca(a,cor[0],preciso[0]);
resp[c]=cor[1];
preciso[1]--;
for(auto x:vizc){
if(preciso[1]==0)continue;
if(resp[x]!=0)continue;
if(tam[x]<=preciso[1]){
preciso[1]-=tam[x];
pintasub(x,c,cor[1]);
}
else{
pintoQnt(x,c,cor[1],preciso[1]);
preciso[1]=0;
}
}
L(i,0,n-1)if(resp[i]==0)resp[i]=cor[2];
return resp;
}
}
return resp;
}
