#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;
}
}
return vector<int>(n);
}
}
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<n-1; ++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 vector<int>(n);
}
