#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define mp make_pair
const int N=2e5+50;
vector<int>E[N],E1[N],G[N];
int n,m;
vector<int>res;
vector<pair<int,int>>splits;
bool was[N];
void DFS(int u){
was[u]=true;
for(auto i:E[u])if(!was[i]){
E1[u].pb(i);
E1[i].pb(u);
DFS(i);
}
}
int sajz[N];
void DFSsetup(int u,int p=-1){
sajz[u]=1;
for(auto i:E1[u])if(i!=p)DFSsetup(i,u),sajz[u]+=sajz[i];
}
int DFSC(int u,int p=-1){
for(auto i:E1[u])if(i!=p&&2*sajz[i]>n)return DFSC(i,u);
return u;
}
struct DSU{
int par[N],sajz[N];
DSU(){Init();}
int FS(int u){if(par[u]==u)return u;return par[u]=FS(par[u]);}
bool US(int u,int v){
u=FS(u),v=FS(v);
if(u==v)return false;
par[u]=v;
sajz[v]+=sajz[u];
return true;
}
int Sajz(int u){return sajz[FS(u)];}
void Init(){for(int i=0;i<N;i++)par[i]=i,sajz[i]=1;}
}dsu;
void Edge(int u,int v){G[u].pb(v),G[v].pb(u);}
pair<int,int>UV;
void DFS1(int u,int p=-1){
sajz[u]=1;
for(auto i:G[u])if(i!=p){
DFS1(i,u);
sajz[u]+=sajz[i];
}
if(p!=-1){
if(sajz[u]>=splits[0].fi&&n-sajz[u]>=splits[1].fi)UV={u,p};
if(n-sajz[u]>=splits[0].fi&&sajz[u]>=splits[1].fi)UV={p,u};
}
}
int DFS2(int u,int num,int col,int p=-1){
if(num<=0||res[u]!=0)return 0;
res[u]=col;num--;
for(auto i:G[u])if(i!=p)num=DFS2(i,num,col,u);
return num;
}
void SolveTree(){
UV={-1,-1};
DFS1(0);
if(UV==mp(-1,-1))return;
DFS2(UV.fi,splits[0].fi,splits[0].se,UV.se);
DFS2(UV.se,splits[1].fi,splits[1].se,UV.fi);
for(int i=0;i<n;i++)if(res[i]==0)res[i]=splits[2].se;
}
vector<int> find_split(int n1,int a,int b,int c,vector<int>p,vector<int>q){
n=n1;m=p.size();
for(int i=0;i<m;i++)E[p[i]].pb(q[i]),E[q[i]].pb(p[i]);
splits={{a,1},{b,2},{c,3}};
sort(splits.begin(),splits.end());
res.resize(n,0);
DFS(0);
DFSsetup(0);
int C=DFSC(0);
for(int i=0;i<n;i++){
for(auto j:E1[i])if(i!=C&&j!=C&&i<j){
Edge(i,j);
dsu.US(i,j);
}
}
bool bul=true;
for(int i=0;i<n;i++)if(i!=C&&dsu.Sajz(i)>=a)bul=false;
if(bul){
for(int i=0;i<m;i++){
if(p[i]!=C&&q[i]!=C&&dsu.US(p[i],q[i])){
Edge(p[i],q[i]);
if(dsu.Sajz(p[i])>=a)break;
}
}
}
bool was1[n+5]={0};
for(auto i:E1[C])if(!was1[dsu.FS(i)]){
Edge(i,C);
was1[dsu.FS(i)]=true;
}
SolveTree();
return res;
}
