#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n, a, b, c;
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(0);
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;
}
}
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;
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();
return vector<int>(n);
}
