#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
int N, ans[MAXN+10];
pii A[4];
vector<int> adj[MAXN+10];
int sz[MAXN+10];
void color(int now, int bef, int col, int &k)
{
if(k<=0) return;
ans[now]=col; k--;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
color(nxt, now, col, k);
}
}
void dfs(int now, int bef)
{
int i, j;
sz[now]=1;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
dfs(nxt, now);
sz[now]+=sz[nxt];
}
if(sz[now]>=A[1].first && N-sz[now]>=A[2].first)
{
for(i=1; i<=N; i++) ans[i]=A[3].second;
int t=A[1].first;
color(now, bef, A[1].second, t);
t=A[2].first;
color(bef, now, A[2].second, t);
}
else if(sz[now]>=A[2].first && N-sz[now]>=A[1].first)
{
for(i=1; i<=N; i++) ans[i]=A[3].second;
int t=A[2].first;
color(now, bef, A[2].second, t);
t=A[1].first;
color(bef, now, A[1].second, t);
}
}
vector<int> find_split(int _N, int _A, int _B, int _C, vector<int> _P, vector<int> _Q)
{
int i, j;
N=_N; A[1]=pii(_A, 1); A[2]=pii(_B, 2); A[3]=pii(_C, 3);
for(i=0; i<_P.size(); i++)
{
int u=_P[i]+1, v=_Q[i]+1;
adj[u].push_back(v);
adj[v].push_back(u);
}
sort(A+1, A+4);
dfs(1, 1);
vector<int> _ans(N);
for(i=1; i<=N; i++) _ans[i-1]=ans[i];
return _ans;
}
