#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], t, res;
void dfs2(int u, int p, int x)
{
if (cnt<=0) return;
res[u]=x;
for (auto v:d[u]) if (v!=p) --cnt, 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]&&max(sz[u], N-sz[u])>=t[1])
{
int a=sz[u], b=N-sz[u];
f=1;
if (a<=b)
{
cnt=t[0];
dfs2(u, p, 1);
cnt=t[1];
dfs2(p, u, 2);
}
else
{
cnt=t[0];
dfs2(p, u, 1);
cnt=t[1];
dfs2(u, p, 2);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N=n;
res.resize(n);
for (int i=0; i<n; i++) res[i]=3;
t.push_back(a), t.push_back(b), t.push_back(c);
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++) res[i]=0;
return res;
}
/*
5 4
1 2 2
0 1
0 2
0 3
0 4
*/
