#include "split.h"
#include "bits/stdc++.h"
using namespace std;
#define vi vector<int>
#define ii pair<int,int>
#define all(x) x.begin(),x.end()
const int mxn=1e5+5;
vi adj[mxn],gra[mxn],res;
vector<ii> ed[mxn];
map<int,ii> temp_gra[mxn];
int timer,act,bad_col;
vi in,prof,id,tam;
vector<bool> is;
vector<vi> groups;
void dfs_cut(int u, int pa){
in[u]=prof[u]=timer++;
int aux=0;
for(int v: adj[u]) if(v!=pa){
if(in[v]==-1){
dfs_cut(v,u);
prof[u]=min(prof[u],prof[v]);
if(prof[v]>=in[u] && pa!=-1) is[u]=true;
aux++;
}
else prof[u]=min(prof[u],in[v]);
}
if(pa==-1 && aux>1) is[u]=true;
}
void find_cut(int n){
timer=0;
in.assign(n,-1); prof.assign(n,-1);
is.assign(n,false);
dfs_cut(0,-1);
}
void find_groups(int u, bool first){
if(is[u]){id[u]=timer; return;}
id[u]=timer;
if(!first) groups[timer].push_back(u);
for(int v: adj[u])
if(id[v]==-1 && !is[v]) find_groups(v,false);
}
void make_size(int u, int pa){
tam[u]=groups[u].size();
for(int v: gra[u]) if(v!=pa){
make_size(v,u);
tam[u]+=tam[v];
}
}
void make_groups(int n){
id.assign(n,-1);
timer=0;
for(int i=0;i<n;i++)
if(id[i]==-1){
groups.push_back({i});
find_groups(i,true);
timer++;
}
for(int u=0;u<n;u++)
if(is[u])
for(int v: adj[u]){
temp_gra[id[u]][id[v]]={u,v};
temp_gra[id[v]][id[u]]={v,u};
}
for(int i=0;i<(int)groups.size();i++){
for(auto x: temp_gra[i]){
gra[i].push_back(x.first);
ed[i].push_back(x.second);
}
}
tam.resize(n);
make_size(0,-1);
}
void paint_group(int u, int act_id, int cant, int col){
if(act>=cant) return;
//printf(" paint %d\n",u);
res[u]=col;
act++;
for(int v: adj[u])
if(id[v]==act_id && res[v]==bad_col) paint_group(v,act_id,cant,col);
}
void paint(int u, int pa, int cant, int col){
if(act>=cant) return;
//printf("in group %d | using %d - %d con\n",u,temp_gra[pa][u].first,temp_gra[pa][u].second);
//printf("group painted:\n");
paint_group(temp_gra[u][pa].first,u,cant,col);
//printf("\n");
for(int v: gra[u])
if(v!=pa) paint(v,u,cant,col);
}
vi find_split(int n, int a, int b, int c, vi p, vi q) {
int m=(int)p.size();
for(int i=0;i<m;i++)
adj[p[i]].push_back(q[i]),adj[q[i]].push_back(p[i]);
find_cut(n);
make_groups(n);
ii col[3]={{a,1},{b,2},{c,3}}; sort(col,col+3);
bad_col=col[2].second;
res.assign(n,bad_col);
/*
printf("left out %d\n\n",bad_col);
for(int i=0;i<(int)groups.size();i++){
printf("%d: ",i);
for(int j: groups[i]) printf("%d ",j);
printf("\n");
}
printf("\n");
*/
vector<ii> con,edge;
for(int i=0;i<(int)groups.size();i++)
for(int j: gra[i])
if(tam[i]>tam[j])
con.push_back({i,j});
bool found=false;
for(int i=0;i<(int)con.size();i++){
int u=con[i].first,v=con[i].second;
int x=n-tam[v],y=tam[v];
if(x>y) swap(u,v),swap(x,y);
if(x<col[0].first || y<col[1].first) continue;
//printf("%d: %d | %d: %d\n",u,x,v,y);
act=0;
//printf("paint from %d: %d %d\n",u,col[0].first,col[0].second);
paint(u,v,col[0].first,col[0].second);
//printf("\n");
act=0;
//printf("paint from %d: %d %d\n",v,col[1].first,col[1].second);
paint(v,u,col[1].first,col[1].second);
//printf("\n");
found=true;
break;
}
/*
vi color[4];
for(int i=0;i<n;i++) color[res[i]].push_back(i);
for(int i=1;i<=3;i++){
printf("%d: ",i);
for(int j: color[i]) printf("%d ",j);
printf(" -> %d\n",(int)color[i].size());
}
printf("\n");
*/
return found ? res : vi (n,0);
}
