#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
const int mxN = 1e5 + 100;
vector<int> adj[mxN];
int par[mxN], sz[mxN], nby2;
vector<int> ans;
int find(int u){
return par[u] = (u == par[u] ? u : find(par[u]));
}
bool unite(int u, int v){
u = find(u), v = find(v);
if(u == v) return 0;
par[u] = v;
return 1;
}
void calc_sz(int u = 0, int par = -1){
sz[u] = 1;
for(auto it : adj[u]){
if(it ^ par){
calc_sz(it, u);
sz[u] += sz[it];
}
}
}
int get_sz(int u, int par){
int ans = 1;
for(auto it : adj[u]){
if(it ^ par) continue;
ans += get_sz(it, u);
}
return ans;
}
int get_cent(int u = 0, int par = -1){
int mx = -1;
for(auto it : adj[u]){
if(it ^ par){
if(mx == -1) mx = it;
else if(sz[mx] < sz[it]) mx = it;
}
}
if(sz[mx] >= nby2){
return get_cent(mx, u);
}
return u;
}
int done = 0;
void work(int u, int par, int cc, int lstc){
if(done <= 0) ans[u] = lstc;
else ans[u] = cc;
for(auto it : adj[u]){
if(it ^ par){
work(it, u, cc, lstc);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m = (int) p.size();
ans.resize(n, -1);
vector<pair<int, int>> ord = {{a, 1}, {b, 2}, {c, 3}};
sort(all(ord));
nby2 = n / 2;
for(int i = 0; i < m; ++i){
if(unite(p[i], q[i])){
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
}
calc_sz();
int cent = get_cent();
for(auto it : adj[cent]){
if(get_sz(it, cent) >= ord[0].fi){
done = ord[0].fi;
work(it, cent, ord[0].se, ord[2].se);
done = ord[1].fi;
work(cent, it, ord[1].se, ord[2].se);
break;
}
}
for(int i = 0; i < n; ++i){
if(ans[i] == -1){
for(int j = 0; j < n; ++j) ans[j] = 0;
break;
}
}
return ans;
}
