#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
const int nax=1e5+5;
int n;
int a, b, c;
int ord[4];
vi graf[nax];
int sz[nax];
void dfs_sz(int u, int p)
{
sz[u]=1;
for (int v:graf[u])
{
if (v==p) continue;
dfs_sz(v, u);
sz[u]+=sz[v];
}
}
int dfsf(int u, int p)
{
for (int v:graf[u])
{
if (v==p) continue;
if (sz[v]>=2*n)
return dfsf(v, u);
}
return u;
}
int centroid()
{
dfs_sz(0, 0);
return dfsf(0, 0);
}
void dfs_down(int u, int p, vi& ans)
{
if (a==0) return;
a--;
assert(ans[u]==0);
ans[u]=ord[1];
for (int v:graf[u])
{
if (v==p) continue;
dfs_down(v, u, ans);
}
}
void dfs_fill2(int u, int p, vi& ans)
{
if (b==0) return;
b--;
assert(ans[u]==0);
ans[u]=ord[2];
for (int v:graf[u])
{
if (v==p) continue;
dfs_fill2(v, u, ans);
}
}
vi find_split(int N, int A, int B, int C, vi u, vi v)
{
n=N; a=A; b=B; c=C;
ord[1]=1;
ord[2]=2;
ord[3]=3;
if (a>c)
{
swap(a,c);
swap(ord[1],ord[3]);
}
if (b>c)
{
swap(b,c);
swap(ord[2],ord[3]);
}
if (a>b)
{
swap(a,b);
swap(ord[1],ord[2]);
}
if (a>c)
{
swap(a,c);
swap(ord[1],ord[3]);
}
if (b>c)
{
swap(b,c);
swap(ord[2],ord[3]);
}
if (a>b)
{
swap(a,b);
swap(ord[1],ord[2]);
}
int m=v.size();
for (int i=0; i<m; i++)
{
graf[u[i]].push_back(v[i]);
graf[v[i]].push_back(u[i]);
}
if (m==n-1)
{
int c=centroid();
dfs_sz(c, c);
for(int v:graf[c])
{
if (sz[v]>=a)
{
vi ans(n);
dfs_down(v, c, ans);
dfs_fill2(c, v, ans);
for (int i=0; i<n; i++)
{
if (ans[i]==0)
{
assert(c>0);
c--;
ans[i]=ord[3];
}
}
return ans;
}
}
vi ans(n);
return ans;
}
}
