#include <bits/stdc++.h>
using namespace std;
int n;
int centroid;
const int N=100000;
vector<int> v[N];
vector<int> g[N];
vector<int> z[N];
vector<int> d;
vector<int> sub(N,0);
vector<int> id(N);
vector<bool> vis(N,0);
vector<int> res;
void dfs1(int a)
{
sub[a]=1;
for(int to:v[a])
{
if(sub[to]!=0) continue;
g[a].push_back(to);
g[to].push_back(a);
dfs1(to);
sub[a]+=sub[to];
}
}
int get_centroid(int a,int p=-1)
{
for(int to:g[a])
{
if(to!=p&&sub[to]>n/2) return get_centroid(to,a);
}
return a;
}
void dfs2(int a,int now)
{
sub[a]=1;
id[a]=now;
for(int to:g[a])
{
if(sub[to]!=0) continue;
if(now==-1) d.push_back(to);
dfs2(to,(now!=-1?now:to));
sub[a]+=sub[to];
}
}
void solve_one(vector<int> src,int num,int t)
{
vector<bool> pos(n,0);
for(int a:src) pos[a]=1;
queue<int> q;
q.push(src[0]);
res[src[0]]=t;
num--;
while(num>0)
{
int e=q.front();
q.pop();
for(int to:v[e])
{
if(to!=centroid&&pos[id[to]]==1&&res[to]==0)
{
q.push(to);
res[to]=t;
num--;
}
if(num==0) break;
}
}
}
void solve_two(int num,int t)
{
queue<int> q;
q.push(centroid);
while(num>0)
{
int e=q.front();
q.pop();
res[e]=t;
num--;
for(int to:g[e]) if(res[to]==0) q.push(to);
}
}
void solve_three(int t)
{
for(int i=0;i<n;i++) if(res[i]==0) res[i]=t;
}
vector<int> component(int src,int a)
{
vector<int> comp;
int cnt=0;
vis[src]=1;
queue<int> q;
q.push(src);
while(!q.empty())
{
int e=q.front();
q.pop();
cnt+=sub[e];
comp.push_back(e);
if(cnt>=a) break;
for(int to:z[e])
{
if(vis[to]) continue;
vis[to]=1;
q.push(to);
}
}
if(cnt>=a) return comp;
else return {-1};
}
vector<int> find_split(int _n,int a,int b,int c,vector<int> ca,vector<int> cb)
{
n=_n;
res.resize(n,0);
int m=ca.size();
for(int i=0;i<m;i++)
{
v[ca[i]].push_back(cb[i]);
v[cb[i]].push_back(ca[i]);
}
dfs1(0);
centroid=get_centroid(0);
for(int i=0;i<n;i++) sub[i]=0;
dfs2(centroid,-1);
vector<pair<int,int>> abc={{a,1},{b,2},{c,3}};
sort(abc.begin(),abc.end());
for(int i=0;i<m;i++)
{
if(ca[i]==centroid||cb[i]==centroid) continue;
if(id[ca[i]]!=id[cb[i]])
{
z[id[ca[i]]].push_back(id[cb[i]]);
z[id[cb[i]]].push_back(id[ca[i]]);
}
}
vector<pair<int,int>> p;
for(int to:d) p.push_back({sub[to],to});
sort(p.begin(),p.end(),greater<pair<int,int>>());
for(pair<int,int> pii:p)
{
int to=pii.second;
if(vis[to]) continue;
vector<int> comp=component(to,abc[0].first);
if(comp[0]==-1) continue;
solve_one(comp,abc[0].first,abc[0].second);
solve_two(abc[1].first,abc[1].second);
solve_three(abc[2].second);
return res;
}
return res;
}
/*int main()
{
vector<int> temp=find_split(9,4,2,3,{0,0,0,0,0,0,1,3,4,5},{1,2,3,4,6,8,7,7,5,6});
for(int a:temp) cout << a << " ";
return 0;
}
*/
