#include "split.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> con[200005];
int n,a,b,c;
int id[3];
int cntv;
vector<int> visited;
void usor(int nod, int b, int val)
{
if(cntv==b)
return;
visited[nod] = val;
cntv++;
for(int adj:con[nod])
if(!visited[adj])
usor(adj,b,val);
}
vector<int> solve_toate_mici()
{
int cntcap=0;
for(int cap=0;cap<n;cap++)
{
if(con[cap].size() == 1)
{
cntcap++;
if(cntcap==1)
{
cntv=0;
usor(cap,a,1);
}
else
{
cntv=0;
usor(cap,b,2);
}
}
}
if(cntcap==0)
{
for(int cap=0;cap<n;cap++)
{
if(visited[cap]==0 && cntcap<2)
{
cntcap++;
if(cntcap==1)
{
cntv=0;
usor(cap,a,1);
}
else
{
cntv=0;
usor(cap,b,2);
}
}
}
}
assert(cntcap==2);
for(int i=0;i<n;i++)
if(visited[i]==0)
visited[i]=3;
return visited;
}
vector<int> solve_a1()
{
usor(0,b,2);
for(int i=0;i<n;i++)
{
if(visited[i]==0)
{
visited[i]=1;
break;
}
}
for(int i=0;i<n;i++)
if(visited[i]==0)
visited[i]=3;
return visited;
}
int siz[200005];
void dfs(int nod, int par)
{
siz[nod]=1;
for(int adj:con[nod])
{
if(adj==par)
continue;
dfs(adj,nod);
siz[nod]+=siz[adj];
}
}
int root1,root2;
void dfs2(int nod, int par)
{
if(root1!=-1)
return;
if(par!=-1 && siz[nod]>=a && n-siz[nod]>=b)
{
root1=nod;
root2=par;
return;
}
if(par!=-1 && siz[nod]>=b && n-siz[nod]>=a)
{
root1=par;
root2=nod;
return;
}
for(int adj:con[nod])
{
if(adj==par)
continue;
dfs2(adj,nod);
}
}
vector<int> solve_arbore()
{
id[0] = 1;
id[1] = 2;
id[2] = 3;
for(int pas=0;pas<5;pas++)
{
if(a > b)
{
swap(a,b);
swap(id[0],id[1]);
}
if(b > c)
{
swap(b,c);
swap(id[1],id[2]);
}
}
dfs(0,-1);
root1=root2=-1;
dfs2(0,-1);
if(root1==-1)
return vector<int>(n,0);
visited[root1] = id[0];
visited[root2] = id[1];
cntv=0;usor(root1,a,id[0]);
cntv=0;usor(root2,b,id[1]);
for(int i=0;i<n;i++)
if(visited[i]==0)
visited[i]=id[2];
return visited;
}
std::vector<int> find_split(int copn, int copa, int copb, int copc, std::vector<int> p, std::vector<int> q)
{
a = copa;
b = copb;
c = copc;
n = copn;
visited.resize(n,0);
for(int i=0;i<p.size();i++)
{
con[p[i]].push_back(q[i]);
con[q[i]].push_back(p[i]);
}
bool all_mici=1;
for(int i=0;i<n;i++)
if(con[i].size() > 2)
all_mici=0;
if(all_mici)
return solve_toate_mici();
else if(a==1)
return solve_a1();
return solve_arbore();
}
