#include <bits/stdc++.h>
#define ll long long
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
#define pii pair <int, int>
const int maxn=2e5+10;
int n, m, a, b, c, col[maxn], sz[maxn], ok;
pii dp1[maxn], dp2[maxn];
vector <int> edge[maxn];
void dfs2(int v, int pred, int TT)
{
if(TT == v)
{
if(a)
{
a--;
col[v] = 1;
}
}
else
{
if(b)
{
b--;
col[v] = 2;
}
}
for(auto to : edge[v])
{
if(to == pred) continue;
if(TT == v)
dfs2(to, v, to);
else
dfs2(to, v, TT);
}
}
void dfs3(int v, int pred, int TT)
{
if(TT == v)
{
if(b)
{
col[v] = 2;
b--;
}
}
else
{
if(a)
{
a--;
col[v] = 1;
}
}
for(auto to : edge[v])
{
if(to == pred) continue;
if(TT == v)
dfs3(to, v, to);
else
dfs3(to, v, TT);
}
}
void dfs(int v, int pred = -1)
{
sz[v] = 1;
dp1[v] = {1e9, 1e9};
dp2[v] = {1e9, 1e9};
for(auto to : edge[v])
{
if(to == pred) continue;
dfs(to, v);
if(ok) return;
sz[v] += sz[to];
dp1[v] = min(dp1[v], dp1[to]);
dp2[v] = min(dp2[v], dp2[to]);
}
if(sz[v] >= a)
{
dp1[v] = min(dp1[v], {sz[v], v});
}
if(sz[v] >= b)
{
dp2[v] = min(dp2[v], {sz[v], v});
}
if(sz[v] - dp1[v].f >= b)
{
dfs2(v, pred, dp1[v].s);
ok = 1;
return;
}
if(sz[v] - dp2[v].f >= a)
{
dfs3(v, pred, dp2[v].s);
ok = 1;
return;
}
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q)
{
n = N;
m = q.size();
forn(1, i, n) edge[i].clear();
ok = 0;
FOR(0, i, m)
{
q[i]++;
p[i]++;
edge[q[i]].pb(p[i]);
edge[p[i]].pb(q[i]);
}
vector <pii> sor;
sor.pb({A, 1});
sor.pb({B, 2});
sor.pb({C, 3});
sort(all(sor));
a = sor[0].f;
b = sor[1].f;
c = sor[2].f;
dfs(1);
// cout << a << " " << b << " " << c << endl;
// forn(1, i, n) cout << col[i] << " ";
// cout << endl;
vector <int> res(n, 0);
if(!ok) return res;
forn(1, i, n)
{
if(col[i] == 0) col[i] = 3;
res[i-1] = sor[col[i]-1].s;
}
return res;
}
