// #include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define fi first
#define se second
#define pb emplace_back
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001;
vector<int> find_split(int n, int A, int B, int C, vector<int> U, vector<int> V) {
vector<int> impossible(n);
ll k=min({A,B,C});
vvi g(n);
rep(i,U.size()){
g[U[i]].pb(V[i]);
g[V[i]].pb(U[i]);
}
vi lk(n,inf),dep(n,-1),par(n),sub(n,1),euler;
function<ll(ll,ll,ll)> dfs=[&](ll i,ll p,ll d){
euler.pb(i);
par[i]=p;dep[i]=d;
for(ll x:g[i])if(x!=p){
if(dep[x]==-1){
sub[i]+=dfs(x,i,d+1);
chmin(lk[i],lk[x]);
}
else chmin(lk[i],dep[x]);
}
return sub[i];
};dfs(0,-1,0);
auto sol=[&](ll sz,vector<bool> flag){
ll i=0;
while(!flag[i])i++;
flag[i]=false;
vi res;
function<void(ll)> dfs=[&](ll cur){
if(res.size()==sz)return;
res.pb(cur);
for(auto x:g[cur])if(flag[x]){
flag[x]=false;
dfs(x);
if(res.size()==sz)return;
}
};dfs(i);
return res;
};
auto answer=[&](vi al){
vb f1(n,false),f2(n,false),f3(n,true);
for(ll i:al)f1[i]=true;
rep(i,n)if(!f1[i])f2[i]=true;
if(al.size()*2>n)swap(f1,f2);
vi a=sol(k,f1),b=sol(n-min({A,B,C})-max({A,B,C}),f2);
for(ll i:a)f3[i]=false;
for(ll i:b)f3[i]=false;
vi c;rep(i,n)if(f3[i])c.pb(i);
if(A!=a.size())swap(a,b);
if(A!=a.size())swap(a,c);
if(B!=b.size())swap(b,c);
vector<int> res(n);
for(ll i:a)res[i]=1;
for(ll i:b)res[i]=2;
for(ll i:c)res[i]=3;
return res;
};
auto get_sub=[&](ll t){
vi res;
function<void(ll)> dfs=[&](ll i){
res.pb(i);
for(ll x:g[i])if(par[x]==i)dfs(x);
};dfs(t);
return res;
};
ll rt;
for(ll i:euler)if(sub[i]*2>=n)rt=i;
for(ll x:g[rt])if(par[x]==rt&&sub[x]>=k)return answer(get_sub(x));
vi al;al.pb(rt);
for(ll x:g[rt])if(par[x]==rt&&lk[x]>=dep[rt]){
vi tmp=get_sub(x);
for(ll y:tmp)al.pb(y);
}
if(al.size()>n-k)return impossible;
for(ll x:g[rt])if(par[x]==rt&&lk[x]<dep[rt]&&al.size()<k){
vi tmp=get_sub(x);
for(ll y:tmp)al.pb(y);
}
return answer(al);
}
