#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define F first
#define S second
const int MN = 1e5+5, MM = 2e5+5;
int N, M, asz, bsz;
struct dsu{
int sz[MN]{}, par[MN]{};
int top(int u){ return par[u] ? par[u] = top(par[u]) : u; }
bool merge(int u, int v){
u = top(u); v = top(v);
if(u == v) return 0;
if(sz[u] > sz[v]) swap(u, v);
par[u] = v; sz[v] += sz[u];
return 1;
}
} dsu1, dsu2;
vector<int> adjl[MN], adjl_all[MN];
namespace centroid{
int sz[MN]{}, col[MN];
void dfs1(int u, int p){
sz[u] = 1;
for(int v: adjl[u]){
if(v != p){
dfs1(v, u);
sz[u] += sz[v];
}
}
}
int find_centroid(int u, int p){
for(int v: adjl[u]){
if(v != p){
if(sz[v] << 1 > N) return find_centroid(v, u);
}
} return u;
}
void dfs2(int u, int p, int c){
++sz[c];
col[u] = c;
for(int v: adjl[u]){
if(v != p){
dfs2(v, u, c);
}
}
}
}
namespace stage_3{
vector<int> adjl2[MN];
bool vis[MN]{};
vector<int> explored;
int tot_sz;
void dfs(int u){
if(tot_sz >= asz) return;
tot_sz += centroid::sz[u];
explored.push_back(u);
vis[u] = 1;
for(int v: adjl2[u]){
if(!vis[v]){
dfs(v);
}
}
}
}
namespace get_ans{
bitset<MN> allowed{}; vector<int> *ans; int c, cnt;
void dfs(int u, int p){
if(--cnt < 0){
return;
}
ans->at(u-1) = c;
for(int v: adjl_all[u]){
if(ans->at(v-1) == 0 && allowed[centroid::col[v]]){
dfs(v, u);
}
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> adjf, vector<int> adjs){
N = n; M = adjf.size();
pii ord[3] = {{a,1}, {b,2}, {c,3}};
sort(ord, ord+3);
asz = ord[0].F; bsz = ord[1].F;
for(int z: {0,1}){
vector<int> &vec = z ? adjf : adjs;
for(int &v: vec){
++v;
}
}
for(int i = 0, u, v; i < M; i++){
u = adjf[i]; v = adjs[i];
if(dsu1.merge(u, v)){
adjl[u].push_back(v);
adjl[v].push_back(u);
}
adjl_all[u].push_back(v);
adjl_all[v].push_back(u);
}
centroid::dfs1(1, -1);
int cent = centroid::find_centroid(1, -1);
memset(centroid::sz, 0, sizeof centroid::sz);
auto find_ans = [&](vector<int> as)->vector<int>{
using namespace get_ans;
vector<int> ret(N);
for(int v: as){
allowed.set(v);
} get_ans::c = ord[0].S; cnt = asz; ans = &ret;
dfs(as[0], cent);
allowed.flip(); get_ans::c = ord[1].S; cnt = bsz;
dfs(cent, -1);
for(int &v: ret){
if(!v){
v = ord[2].S;
}
}
return ret;
};
for(int u: adjl[cent]){
centroid::dfs2(u, cent, u);
if(centroid::sz[u] >= asz){
return find_ans({u});
}
}
for(int i = 0, u, v; i < M; i++){
u = adjf[i]; v = adjs[i];
if(u == cent || v == cent) continue;
u = centroid::col[u]; v = centroid::col[v];
if(dsu2.merge(u, v)){
stage_3::adjl2[u].push_back(v);
stage_3::adjl2[v].push_back(u);
}
}
for(int u: adjl[cent]){
if(!stage_3::vis[u]){
stage_3::explored.clear(); stage_3::tot_sz = 0;
stage_3::dfs(u);
if(stage_3::tot_sz >= asz){
return find_ans(stage_3::explored);
}
}
}
return vector<int>(N);
}
