#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], adj2[MAXN+10], adj3[MAXN+10];
int sz[MAXN+10], id[MAXN+10];
void getsz(int now, int bef)
{
sz[now]=1;
for(int nxt : adj2[now])
{
if(nxt==bef) continue;
getsz(nxt, now);
sz[now]+=sz[nxt];
}
}
int getcen(int now, int bef, int S)
{
for(int nxt : adj2[now])
{
if(nxt==bef) continue;
if(sz[nxt]>S/2) return getcen(nxt, now, S);
}
return now;
}
void color(int now, int bef, int col, int &k)
{
if(k<=0) return;
ans[now]=col; k--;
for(int nxt : adj2[now])
{
if(nxt==bef) continue;
if(ans[nxt]) continue;
color(nxt, now, col, k);
}
}
void color2(int now, int bef, int root)
{
id[now]=root;
for(int nxt : adj2[now])
{
if(nxt==bef) continue;
color2(nxt, now, root);
}
}
bool vis[MAXN+10];
void dfs(int now)
{
vis[now]=true;
for(int nxt : adj[now])
{
if(vis[nxt]) continue;
adj2[now].push_back(nxt);
adj2[nxt].push_back(now);
dfs(nxt);
}
}
vector<int> V;
void dfs2(int now, int &k)
{
vis[now]=true;
k+=sz[now]; V.push_back(now);
if(k>=A[1].first) return;
for(int nxt : adj3[now])
{
if(vis[nxt]) continue;
dfs2(nxt, k);
}
}
void solve()
{
int i, j;
memset(vis, 0, sizeof(vis));
dfs(1);
getsz(1, 1);
int cen=getcen(1, 1, N);
getsz(cen, cen);
for(int now : adj2[cen])
{
color2(now, cen, now);
if(A[1].first<=sz[now])
{
int t=A[1].first;
color(now, cen, A[1].second, t);
t=A[2].first;
color(cen, now, A[2].second, t);
for(i=1; i<=N; i++) if(ans[i]==0) ans[i]=A[3].second;
return;
}
}
for(i=1; i<=N; i++)
{
int now=i;
if(now==cen) continue;
for(int nxt : adj[now])
{
if(nxt==cen) continue;
if(id[now]==id[nxt]) continue;
adj3[id[now]].push_back(id[nxt]);
}
}
memset(vis, 0, sizeof(vis));
for(int now : adj2[cen])
{
if(vis[now]) continue;
int t=0;
dfs2(now, t);
if(t<A[1].first) continue;
t=A[1].first;
for(auto it : V) color(it, cen, A[1].second, t);
color(cen, cen, A[2].second, A[2].first);
for(i=1; i<=N; i++) if(ans[i]==0) ans[i]=A[3].second;
return;
}
}
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);
solve();
vector<int> _ans(N);
for(i=1; i<=N; i++) _ans[i-1]=ans[i];
return _ans;
}
