#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n, a, b, c, m;
vector<int> g[N];
namespace sub1{
bool check(){
for (int i=0; i<n; ++i) if ((int)g[i].size()>2) return 0;
return 1;
}
vector<int> path;
int vis[N];
void dfs(int u){
vis[u]=1;
path.push_back(u);
for (int v:g[u]) if (!vis[v]) dfs(v);
}
vector<int> solve(){
int u=0;
for (int i=0; i<n; ++i) if (g[i].size()==1) u=i;
dfs(u);
vector<int> ans(n);
for (int i=0; i<n; ++i){
if (i<a) ans[path[i]]=1;
else if (i<a+b) ans[path[i]]=2;
else ans[path[i]]=3;
}
return ans;
}
}
namespace sub2{
int num[N], low[N], joint[N], tdfs;
bool check(){
return a==1;
}
void dfs(int u, int p){
num[u]=low[u]=++tdfs;
int cc=0;
for (int v:g[u]) if (v!=p){
if (!num[v]){
++cc;
dfs(v, u);
low[u]=min(low[u], low[v]);
if (low[v]>=num[u]) joint[u]=1;
}else low[u]=min(low[u], num[v]);
}
if (p==-1) joint[u]=cc>=2;
}
void dfs2(int u, int &cnt, vector<int> &ans){
if (cnt==0) return;
ans[u]=2;
--cnt;
if (cnt==0) return;
for (int v:g[u]) if (ans[v]==3){
dfs2(v, cnt, ans);
if (cnt==0) return;
}
}
vector<int> solve(){
dfs(0, -1);
int u=0;
while (joint[u]) ++u;
vector<int> ans(n, 3);
ans[u]=1;
dfs2(u==0?1:0, b, ans);
return ans;
}
}
namespace sub3{
bool check(){
return m==n-1;
}
int sz[N];
void dfs(int u, int p){
sz[u]=1;
for (int v:g[u]) if (v!=p){
dfs(v, u);
sz[u]+=sz[v];
}
}
vector<pair<int, int>> vv;
void dfs2(int u, int &cnt, int z, vector<int> &ans){
if (cnt==0) return;
ans[u]=z;
--cnt;
if (cnt==0) return;
for (int v:g[u]) if (ans[v]==vv[2].second){
dfs2(v, cnt, z, ans);
if (cnt==0) return;
}
}
vector<int> solve(){
vv={{a, 1}, {b, 2}, {c, 3}};
sort(vv.begin(), vv.end());
dfs(0, -1);
vector<int> ans(n, vv[2].second);
for (int i=0; i<n; ++i) for (int j:g[i]) if (sz[i]>sz[j]){
if (sz[j]>=vv[0].first && n-sz[j]>=vv[1].first){
ans[j]=vv[0].second;
ans[i]=vv[1].second;
dfs2(j, vv[0].first, vv[0].second, ans);
dfs2(i, vv[1].first, vv[1].second, ans);
return ans;
}
if (sz[j]>=vv[1].first && n-sz[j]>=vv[0].first){
ans[i]=vv[0].second;
ans[j]=vv[1].second;
dfs2(i, vv[0].first, vv[0].second, ans);
dfs2(j, vv[1].first, vv[1].second, ans);
return ans;
}
}
return vector<int>(n);
}
}
namespace sub4{
int vis[N], num[N], low[N], joint[N], tdfs, sz[N], del[N];
int da, db, dc;
vector<int> vj;
stack<pair<int, int>> st;
int cnt;
set<int> bcc[N];
vector<int> gg[N];
int id[N];
void dfs(int u, int p){
num[u]=low[u]=++tdfs;
int cc=0;
for (int v:g[u]) if (v!=p){
if (!num[v]){
++cc;
st.emplace(u, v);
dfs(v, u);
low[u]=min(low[u], low[v]);
if (low[v]>=num[u]){
joint[u]=1;
pair<int, int> w;
do{
w=st.top();
st.pop();
bcc[cnt].insert(w.first);
bcc[cnt].insert(w.second);
}while (w!=make_pair(u, v));
++cnt;
}
}else low[u]=min(low[u], num[v]);
}
if (p==-1) joint[u]=cc>=2;
if (joint[u]) vj.push_back(u);
}
int par[N];
void dfs2(int u, int p){
par[u]=p;
if (u>=n) sz[u]=bcc[u-n].size();
int cc=0;
for (int v:gg[u]) if (v!=p){
dfs2(v, u);
sz[u]+=sz[v];
++cc;
}
if (u<n) sz[u]-=max(0, cc-1);
else sz[u]-=cc;
}
vector<int> ans;
void color1(int u, int &x, int dx){
if (x==0) return;
ans[u]=dx;
del[u]=1;
--x;
if (x==0) return;
for (int v:g[u]) if (!del[v] && ans[v]==dc){
color1(v, x, dx);
if (x==0) return;
}
}
int it;
void dfs3(int u, int p){
vis[u]=it;
num[u]=low[u]=++tdfs;
int cc=0;
for (int v:g[u]) if (v!=p && !del[v]){
if (vis[v]!=it){
++cc;
dfs3(v, u);
low[u]=min(low[u], low[v]);
if (low[v]>=num[u]) joint[u]=1;
}else low[u]=min(low[u], num[v]);
}
if (p==-1) joint[u]=cc>=2;
if (joint[u]) vj.push_back(u);
}
void color2(int u, int x, int dx, int y, int dy){
if (x==0){
for (int v:g[u]) if (!del[v] && ans[v]==dc){
color1(v, y, dy);
}
return;
}
set<int> adj;
while (1){
ans[u]=dx;
--x;
adj.erase(u);
for (int v:g[u]) if (!del[v]) adj.insert(v);
++it;
del[u]=1;
for (int v:adj){
if (vis[v]!=it) dfs3(v, -1);
if (!joint[v]){
u=v;
break;
}
}
assert(!del[u]);
if (x==0) break;
}
for (int v:adj) if (ans[v]==dc) color1(v, y, dy);
}
bool test(int u){
++it;
vector<pair<int, pair<int, int>>> vc;
for (int v:gg[u]){
vc.push_back({v, {par[v]==u?sz[v]-1:n-sz[u], (int)bcc[v-n].size()-1}});
}
for (auto &p:vc){
if (p.second.first>=b && n-p.second.first+min(p.second.second-1, p.second.first-b)>=a){
del[u]=1;
ans=vector<int>(n, dc);
ans[u]=da;
--a;
for (auto &q:vc) if (q!=p){
int d=min(a, q.second.first);
a-=d;
for (int v:bcc[q.first-n]) if (v!=u){
color1(v, d, da);
break;
}
}
color2(u, a, da, b, db);
return 1;
}
if (p.second.first>=a && n-p.second.first+min(p.second.second-1, p.second.first-a)>=b){
del[u]=1;
ans=vector<int>(n, dc);
ans[u]=db;
--b;
for (auto &q:vc) if (q!=p){
int d=min(b, q.second.first);
b-=d;
for (int v:bcc[q.first-n]) if (v!=u){
color1(v, d, db);
break;
}
}
color2(u, b, db, a, da);
return 1;
}
}
return 0;
}
vector<int> solve(){
da=1; db=2; dc=3;
if (a>b) swap(a, b), swap(da, db);
if (a>c) swap(a, c), swap(da, dc);
if (b>c) swap(b, c), swap(db, dc);
ans=vector<int>(n);
dfs(0, -1);
for (int i=0; i<n; ++i) if (joint[i]) id[i]=i;
for (int i=0; i<cnt; ++i){
for (int j:bcc[i]){
if (!joint[j]) id[j]=n+i;
else gg[n+i].push_back(j), gg[j].push_back(n+i);
}
}
dfs2(n, -1);
if (vj.empty()){
ans=vector<int>(n, dc);
color2(0, a, da, b, db);
}else{
for (int u:vj){
if (test(u)) break;
}
}
return ans;
}
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
n=_n, a=_a, b=_b, c=_c;
m=p.size();
for (int i=0; i<m; ++i) g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]);
// if (sub1::check()) return sub1::solve();
// if (sub2::check()) return sub2::solve();
// if (sub3::check()) return sub3::solve();
return sub4::solve();
}
