#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 1;
vector<int> nei[M], v, ans;
int subt[M];
bool vis[M];
void find(int u,int sz)
{
v.push_back(u);
vis[u]=1;
if (v.size()==sz) return;
for (int i:nei[u])
if (!vis[i])
find(i,sz);
}
void dfs(int u,int p=-1)
{
subt[u]=1;
for (int i:nei[u])
if (i!=p)
{
dfs(i,u);
subt[u]+=subt[i];
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
int m=p.size();
for (int i=0;i<m;i++)
nei[p[i]].push_back(q[i]), nei[q[i]].push_back(p[i]);
ans=vector<int>(n);
if (m==n-1)
{
dfs(0);
bool dn=0;
for (int i=0;i<n && !dn;i++)
{
vector<int> d={a,b,c};
for (int j=0;j<3 && !dn;j++)
for (int k=0;k<3 && !dn;k++)
{
if (j==k) continue;
if (subt[i]>=d[j] && n-subt[i]>=d[k])
{
find(i,d[j]);
for (int u:v)
ans[i]=j+1;
v.clear();
find(1,d[k]);
for (int u:v)
ans[i]=k+1;
for (int u=0;u<n;u++)
if (!ans[u])
ans[u]=6-j-k-2;
dn=1;
}
}
}
return ans;
}
else if(a==1)
{
find(0,b);
for (int i:v)
ans[i]=2;
for (int i=0;i<n;i++)
if (!ans[i])
{
ans[i]=1;
break;
}
for (int i=0;i<n;i++)
if (!ans[i]) ans[i]=3;
return ans;
}
else
{
find(0,a);
for (int i:v)
ans[i]=1;
for (int i=0;i<n;i++)
if (!vis[i])
{
v.clear();
find(i,b);
}
for (int i:v)
ans[i]=2;
for (int i=0;i<n;i++)
if (!ans[i]) ans[i]=3;
return ans;
}
}
