#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#include <split.h>
#define mp make_pair
#define pb push_back
/*#define a first
#define b second*/
vector<int> adj[200001];
vector<int> stac;
int bb;
int aa;
int cc;
int ind7;
int ind2=0;
int co=0;
int vis[200001];
int dd;
vector<int> anss;
void dfs(int no){
stac.pb(no);
if(stac.size()==bb){
return ;
}
for(int j=0;j<adj[no].size();j++){
if(stac.size()==bb){
return;
}
int nn=adj[no][j];
if(vis[nn]==0){
vis[nn]=1;
dfs(nn);
}
}
}
void dfs2(int no){
co+=1;
if(co<=aa){
anss[no]=1;
}
else if(co<=aa+bb){
anss[no]=2;
}
else{
anss[no]=3;
}
for(int j=0;j<adj[no].size();j++){
int nn=adj[no][j];
if(vis[nn]==0){
vis[nn]=1;
dfs2(nn);
}
}
}
int size2[200001];
vector<pair<int,int>> pos;
void dfs3(int no,int par=-1){
size2[no]=1;
int st=1;
for(int j=0;j<adj[no].size();j++){
int nn=adj[no][j];
if(nn==par){
continue;
}
dfs3(nn,no);
size2[no]+=size2[nn];
if(size2[nn]>=aa){
st=0;
}
}
if(st==1 and size2[no]>=aa){
pos.pb(mp(no,par));
}
}
int val[3];
void dfs4(int no,int par){
co+=1;
anss[no]=val[0];
if(co==aa){
return;
}
for(int j=0;j<adj[no].size();j++){
if(co==aa){
return;
}
int nn=adj[no][j];
if(nn==par){
continue;
}
if(ind7==nn){
continue;
}
dfs4(nn,no);
}
}
void dfs5(int no,int par){
co+=1;
anss[no]=val[1];
if(co==bb){
return;
}
for(int j=0;j<adj[no].size();j++){
if(co==aa){
return;
}
int nn=adj[no][j];
if(nn==par){
continue;
}
if(ind7==nn){
continue;
}
dfs5(nn,no);
}
}
vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q){
int m=p.size();
bb=b;
aa=a;
cc=c;
memset(vis,0,sizeof(vis));
for(int i=0;i<m;i++){
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
if(a==1){
//st2
vis[0]=1;
dfs(0);
int st2=1;
vector<int> ans;
for(int i=0;i<n;i++){
ans.pb(0);
}
for(int j=0;j<b;j++){
ans[stac[j]]=2;
}
for(int i=0;i<n;i++){
if(ans[i]==2){
continue;
}
ans[i]=st2;
st2=3;
}
return ans;
}
int st=0;
int ind=-1;
for(int i=0;i<n;i++){
anss.pb(0);
}
for(int i=0;i<n;i++){
if(adj[i].size()>2){
st=1;
}
else if(adj[i].size()==1){
ind=i;
}
}
if(st==1){
if(m==n-1){
vector<int> ss;
ss.pb(a);
ss.pb(b);
ss.pb(c);
sort(ss.begin(),ss.end());
for(int i=0;i<3;i++){
if(ss[i]==a){
val[0]=1;
}
else if(ss[i]==b){
val[0]=2;
}
else{
val[0]=3;
}
}
a=ss[0];
b=ss[1];
c=ss[2];
aa=a;
bb=b;
cc=c;
dfs3(0,-1);
ind7=-1;
int par5=-1;
/* for(int i=0;i<n;i++){
cout<<size[i]<<" ";
}
cout<<endl;*/
for(int j=0;j<pos.size();j++){
if(n-size2[pos[j].first]>=a){
ind7=pos[j].first;
par5=pos[j].second;
break;
}
}
if(ind7==-1){
return anss;
}
if(size2[ind7]<b){
int ind8=ind7;
ind7=0;
dfs4(ind8,par5);
ind7=ind8;
dfs5(0,-1);
for(int i=0;i<n;i++){
if(anss[i]==0){
anss[i]=val[2];
}
}
}
else{
int ind8=ind7;
ind7=0;
dfs5(ind8,par5);
ind7=ind8;
dfs4(0,-1);
for(int i=0;i<n;i++){
if(anss[i]==0){
anss[i]=val[2];
}
}
}
return anss;
}
vector<int> rip;
return rip;
}
else{
//st1
if(ind==-1){
ind=0;
}
vis[ind]=1;
dfs2(ind);
}
return anss;
}
/*int main(){
vector<int> ans10;
ans10=find_split(6, 2, 3, 1, {0, 1, 2, 3, 4}, {1, 2, 3, 4, 5});
for(int i=0;i<ans10.size();i++){
cout<<ans10[i]<<endl;
}
return 0;
}*/
