#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 4e5+10;
vector<int> ans;
int N,A,B,C;
int sz[mxn],wei[mxn];
vector<int> paths[mxn],tree[mxn];
vector<int> gp[mxn];
vector<int> perm;
vector<int> tar;
int gcnt = 0;
namespace BCC{
int idx[mxn],low[mxn];
int cnt = 0;
vector<int> st;
void dfs(int now,int par){
idx[now] = low[now] = ++cnt;
st.push_back(now);
for(auto nxt:paths[now]){
if(!idx[nxt]){
dfs(nxt,now);
low[now] = min(low[now],low[nxt]);
if(low[nxt] == idx[now]){
gcnt++;
while(st.back() != nxt){
gp[st.back()].push_back(gcnt);
tree[st.back()].push_back(gcnt+N);
tree[gcnt+N].push_back(st.back());
st.pop_back();
}
gp[st.back()].push_back(gcnt);
tree[st.back()].push_back(gcnt+N);
tree[gcnt+N].push_back(st.back());
st.pop_back();
gp[now].push_back(gcnt);
tree[now].push_back(gcnt+N);
tree[gcnt+N].push_back(now);
}
}
else{
low[now] = min(low[now],idx[nxt]);
}
}
return;
}
void GO(){
dfs(0,0);
return;
}
}
void dfs(int now,int par){
sz[now] = wei[now];
for(auto nxt:tree[now]){
if(nxt == par)continue;
dfs(nxt,now);
sz[now] += sz[nxt];
}
return;
}
int find_centroid(int now,int par,int tar){
for(auto nxt:tree[now]){
if(nxt == par)continue;
if(sz[nxt]>tar)return find_centroid(nxt,now,tar);
}
return now;
}
void color(int now,int par,int &cnt,int col){
if(!cnt)return;
cnt-=wei[now];
if(now<N)ans[now] = col;
for(auto nxt:tree[now]){
if(nxt == par)continue;
color(nxt,now,cnt,col);
}
return;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
ans = vector<int>(n,0);
N = n,A = a,B = b,C = c;
tar = {A,B,C};
perm = {0,1,2};
sort(perm.begin(),perm.end(),[&](int a,int b){return tar[a]<tar[b];});
sort(tar.begin(),tar.end());
fill(wei,wei+N,1);
for(int i = 0;i<p.size();i++){
int a = p[i],b = q[i];
paths[a].push_back(b);
paths[b].push_back(a);
}
BCC::GO();
/*
for(int i = 0;i<=N+gcnt;i++){
for(auto nxt:tree[i]){
if(nxt>i)cerr<<i<<','<<nxt<<endl;
}
}
cerr<<gcnt<<endl;
*/
color(0,0,tar[1],perm[1]+1);
for(auto &i:ans){
if(!i){
i = perm[0]+1;
break;
}
}
for(auto &i:ans)if(!i)i = perm[2]+1;
return ans;
}
