#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 1;
vector<int> nei[M], v, ans;
int subt[M], mn[M], dep[M];
bool vis[M];
void find(int u,int sz)
{
v.push_back(u);
vis[u]=1;
if (v.size()==sz) return;
for (int i:nei[u])
if (!vis[i])
{
find(i,sz);
if (v.size()==sz) return;
}
}
void dfs(int u)
{
subt[u]=1, vis[u]=1, mn[u]=dep[u];
for (int i:nei[u])
{
if (!vis[i])
{
dep[i]=dep[u]+1, dfs(i);
subt[u]+=subt[i], mn[u]=min(mn[u],mn[i]);
}
mn[u]=min(mn[u],dep[i]);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
ans=vector<int>(n);
vector<pair<int,int>> v1={{a,1},{b,2},{c,3}};
sort(v1.begin(),v1.end());
a=v1[0].first, b=v1[1].first, c=v1[2].first;
int id[3];
for (int j=0;j<3;j++) id[j]=v1[j].second;
for (int i=0;i<n-1;i++)
nei[p[i]].push_back(q[i]),
nei[q[i]].push_back(p[i]);
dfs(0);
for (int i=0;i<n;i++) vis[i]=0;
int u=0;
while (1)
{
vis[u]=1;
bool p=1;
for (int i:nei[u])
if (!vis[i] && subt[i]>=a)
{
u=i, p=0;
break;
}
if (p) break;
}
if (n-subt[u]<a)
{
int tot=n-subt[u];
vector<int> v;
for (int i:nei[u])
if (dep[i]==dep[u]+1)
v.push_back(i);
nei[u].clear();
for (int i:v)
if (mn[i]>=dep[u] or tot>=a)
nei[u].push_back(i);
else
tot+=subt[i];
}
for (int i=0;i<n;i++) vis[i]=0;
if (n-subt[u]>=a)
{
int cnt, cnt1, c, c1;
vis[u]=1;
queue<int> q;
q.push(u);
if (subt[u]>=n-subt[u])
cnt=b-1, cnt1=a, c=id[1], c1=id[0];
else
cnt=a-1, cnt1=b, c=id[0], c1=id[1];
ans[u]=c;
while (cnt)
{
int v=q.front();q.pop();
for (int i:nei[v])
{
if (!vis[i] && dep[i]>dep[u])
vis[i]=1, ans[i]=c, cnt--, q.push(i);
if (!cnt) break;
}
}
find(0,cnt1);
for (int i:v)
ans[i]=c1;
for (int i=0;i<n;i++)
if (!ans[i])
ans[i]=id[2];
}
return ans;
}
