#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5;
int N, sz[nx], f, cnt;
vector<int> d[nx], res;
vector<pair<int, int>> t;
void dfs2(int u, int p, int x)
{
res[u]=x;
cnt--;
for (auto v:d[u]) if (v!=p&&cnt>0) dfs2(v, u, x);
}
void dfs(int u, int p)
{
sz[u]=1;
for (auto v:d[u]) if (v!=p) dfs(v, u), sz[u]+=sz[v];
if (p!=u&&!f&&min(sz[u], N-sz[u])>=t[0].first&&max(sz[u], N-sz[u])>=t[1].first)
{
int a=sz[u], b=N-sz[u];
f=1;
if (a<=b)
{
cnt=t[0].first;
dfs2(u, p, t[0].second);
cnt=t[1].first;
dfs2(p, u, t[1].second);
}
else
{
cnt=t[0].first;
dfs2(p, u, t[0].second);
cnt=t[1].first;
dfs2(u, p, t[1].second);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N=n;
res.resize(n);
t.push_back({a, 1}), t.push_back({b, 2}), t.push_back({c, 3});
sort(t.begin(), t.end());
for (int i=0; i<n-1; i++) d[p[i]].push_back(q[i]), d[q[i]].push_back(p[i]);
dfs(0, 0);
if (f) for (int i=0; i<N; i++) if (res[i]==0) res[i]=t[2].second;
return res;
}
/*
5 4
1 2 2
0 1
0 2
0 3
0 4
*/
