#include <cstdio>
#include <cassert>
using namespace std;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> G[100005];
vector<int> v,sts,v2;
ll pl=0, temp;
ll dfs(ll node,ll Padre)
{
if(v2[node]!=0) return 0;
v2[node]=1;
sts[node]=1;
for(auto i:G[node])
{
if(i!=Padre)
sts[node]+=dfs(i,node);
}
if(sts[node]>=temp&&pl==0)
{
pl=1;
temp=node;
}
return sts[node];
}
void fill(ll node, ll c, ll color)
{
queue<ll> q;
v[node]=color;c--;
q.push(node);
while(!q.empty())
{
for(auto i:G[q.front()])
{
if(sts[i]<sts[q.front()]&&c>0&&v[i]==0)
{
v[i]=color;
c--;
q.push(node);
}
}
q.pop();
}
}
void fill2(ll node, ll c, ll color)
{
queue<ll> q;
v[node]=color;c--;
q.push(node);
while(!q.empty())
{
for(auto i:G[q.front()])
{
if(c>0&&v[i]==0)
{
v[i]=color;
c--;
q.push(i);
}
}
q.pop();
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
for(int i=0; i<p.size(); i++)
{
G[p[i]].push_back(q[i]);
G[q[i]].push_back(p[i]);
}
pair<ll,ll> cad[]={{a,1},{b,2},{c,3}}; sort(cad,cad+3); temp=cad[0].first;
v.assign(n,0); sts.assign(n,0),v2.assign(n,0);
dfs(0,-1);
if(n-sts[temp]<cad[0].first)
{
return v;
}
if(sts[temp]*2>n)
{
swap(cad[0],cad[1]);
}
fill(temp,cad[0].first,cad[0].second);
fill2(0,cad[1].first,cad[1].second);
for(int i=0; i<n; i++)
{
if(v[i]==0)
{
v[i]=cad[2].second;
}
}
return v;
}
