#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include "split.h"
using namespace std;
const int MAX_N=1e5+5;
vector<int>cg[MAX_N];
int col[MAX_N];
int decg[MAX_N];
int A,B;
int whA,whB;
int parent[MAX_N];
int sz[MAX_N];
void dfss(int u,int pare)
{
sz[u]=1;
for(int v:cg[u])
{
if(v==pare)continue;
decg[u]++;
decg[v]++;
parent[v]=u;
dfss(v,u);
sz[u]+=sz[v];
}
}
int ban=-1;
void colour(int u,int color)
{
if(u==-1)while(1);
col[u]=color;
for(int v:cg[u])
{
if(col[v]==color or v==ban)continue;
colour(v,color);
}
}
vector<int>ans;
vector<pair<int,int>>shit;
int N;
void solve()
{
queue<int>bfs;
int cntwhA=0;
for(int i=0;i<N;i++)
{
if(col[i]==whA)
{
cntwhA++;
if(decg[i]==1)bfs.push(i);
}
}
int toremove=cntwhA-A;
while(bfs.size()>0 && toremove>0)
{
int u=bfs.front();
bfs.pop();
toremove--;
col[u]=shit[2].second;
for(int v:cg[u])
{
if(col[v]==whA)
{
decg[v]--;
if(decg[v]==1)bfs.push(v);
}
}
}
while(bfs.size()>0)bfs.pop();
int cntwhB=0;
for(int i=0;i<N;i++)
{
if(col[i]==whB)
{
cntwhB++;
if(decg[i]==1)bfs.push(i);
}
}
toremove=cntwhB-B;
while(bfs.size()>0 && toremove>0)
{
int u=bfs.front();
bfs.pop();
toremove--;
col[u]=shit[2].second;
for(int v:cg[u])
{
if(col[v]==whB)
{
decg[v]--;
if(decg[v]==1)bfs.push(v);
}
}
}
//B
for(int i=0;i<N;i++)ans[i]=col[i];
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
N=n;
ans.resize(n);
for(int i=0;i<n;i++)
{
col[i]=0;
cg[i].clear();
decg[i]=0;
}
shit.clear();
shit.push_back({a,1});
shit.push_back({b,2});
shit.push_back({c,3});
sort(shit.begin(),shit.end());
A=shit[0].first;whA=shit[0].second;
B=shit[1].first;whB=shit[1].second;
for(int ii=0;ii<((int)p.size());ii++)
{
cg[p[ii]].push_back(q[ii]);
cg[q[ii]].push_back(p[ii]);
}
parent[0]=-1;
dfss(0,-1);
return ans;
vector<pair<int,int>>subtrees;
for(int i=0;i<n;i++)
{
subtrees.clear();
int all=1;
for(int u:cg[i])
{
if(u==parent[i])continue;
subtrees.push_back({sz[u],u});
all+=sz[u];
}
if(i>0)subtrees.push_back({n-all,parent[i]});
sort(subtrees.begin(),subtrees.end());
int firstA=-1,firstB=-1;
for(auto [s,u]:subtrees)
{
if(s>=A && firstA==-1)
{
firstA=u;
}
if(s>=B && firstB==-1)
{
firstB=u;
}
}
if(firstA==-1)continue;
if(n-sz[firstA]>=B)
{
colour(0,whB);
ban=i;
colour(firstA,whA);
solve();
return ans;
}
else if(firstB!=-1 && n-sz[firstB]>=A)
{
colour(0,whA);
ban=i;
colour(firstB,whB);
solve();
return ans;
}
else continue;
}
return ans;
}
