#include "split.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
using namespace std;
typedef vector<int> vi;
const int MxN=1e5+10;
int n, m, dp[MxN], s[3];
bool v[MxN];
vi ad[MxN];
void pre(int u, int pst=-1) {
dp[u]=1;
for(auto it : ad[u]) {
if(it==pst) continue;
pre(it, u);
dp[u]+=dp[it];
}
}
bool rev=false;
int x=-1, y=-1;
void dfs(int u, int pst=-1, int up=0) {
if(up>=s[0] && dp[u]>=s[1]) {
rev=false;
x=pst; y=u;
}
else if(up>=s[1] && dp[u]>=s[0]) {
rev=true;
x=u; y=pst;
}
for(auto it : ad[u]) {
if(it==pst) continue;
dfs(it, u, up+dp[u]-dp[it]);
}
}
vi ans;
void spread(int u, int in, int pst=-1) {
s[in]--;
ans[u]=in+1;
if(s[in]==0) return;
for(auto it : ad[u]) {
if(v[it] || it==pst) continue;
spread(it, in, u);
if(s[in]==0) return;
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n=N; m=p.size();
vi tmp; tmp.pb(a); tmp.pb(b); tmp.pb(c);
//sort(tmp.begin(), tmp.end());
FOR(z, 0, 3) s[z]=tmp[z];
FOR(i, 0, m) {
ad[p[i]].pb(q[i]);
ad[q[i]].pb(p[i]);
}
pre(0);
dfs(0);
FOR(i, 0, n) ans.pb(0);
if(x==-1) return ans;
FOR(i, 0, n) ans[i]=3;
v[x]=v[y]=true;
spread(x, rev);
spread(y, !rev);
// cout << x << " " << y << endl;
return ans;
}
