#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+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, del[N];
int da, db, dc;
int it;
vector<int> vj;
void dfs(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;
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==0) joint[u]=cc>=2;
if (joint[u]) vj.push_back(u);
}
vector<int> ans;
void color1(int u, int &x, int dx){
if (x==0) return;
ans[u]=dx;
--x;
if (x==0) return;
for (int v:g[u]) if (!del[v] && ans[v]==dc){
color1(v, x, dx);
if (x==0) return;
}
}
void color2(int u, int x, int dx, int y, int dy){
if (x==0) return color1(u, y, dy);
vector<int> adj;
while (1){
ans[u]=dx;
--x;
adj.clear();
for (int v:g[u]) if (!del[v]) adj.push_back(v);
++it;
del[u]=1;
for (int v:adj){
if (vis[v]!=it) dfs(v, 0);
if (!joint[v]){
u=v;
break;
}
}
assert(!del[u]);
if (x==0) break;
}
color1(u, y, dy);
}
void dnc(int u){
++it;
tdfs=0;
vj.clear();
dfs(u, 0);
int csz=tdfs;
if (csz<a+b) return;
if (vj.empty()){
ans=vector<int>(dc);
color2(u, a, da, b, db);
return;
}
u=vj[0];
++it;
del[u]=1;
vector<pair<int, int>> vc;
for (int v:g[u]) if (!del[v] && vis[v]!=it){
tdfs=0;
dfs(v, 0);
vc.emplace_back(v, tdfs);
}
for (auto &p:vc){
if (p.second>=b){
ans=vector<int>(n, dc);
ans[u]=da;
--a;
for (auto &q:vc) if (q!=p){
int d=min(a, q.second);
a-=d;
color1(q.first, d, da);
}
color2(p.first, a, da, b, db);
return;
}
if (p.second>=a){
ans=vector<int>(n, dc);
ans[u]=db;
--b;
for (auto &q:vc) if (q!=p){
int d=min(b, q.second);
color1(q.first, d, db);
b-=d;
}
color2(p.first, b, db, a, da);
return;
}
}
}
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);
dnc(0);
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();
}
