#include <bits/stdc++.h>
#include "split.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)1e5 + 10;
vector<int> T[N];
vector<int> R[N];
int subt[N];
pii S[3];
bool vis[N];
vector<int> nds[N];
void dfs(int u){
vis[u]=true;
subt[u]=1;
for(auto x : T[u]){
if(vis[x]) continue;
dfs(x);
subt[u] += subt[x];
R[u].push_back(x);
R[x].push_back(u);
}
}
int id[N];
int sub[N];
int cnt;
void dfs1(int u, int cc){
sub[u] = 1;
id[u] = cc;
nds[cc].push_back(u);
for(auto x : R[u]){
if(id[x] == -1){
dfs1(x, cc);
sub[u] += sub[x];
}
}
}
vector<int> spi;
void do_sp(int node, int ci){
if(spi[node] > 0) return ;
if(S[ci].fi > 0){
S[ci].fi -- ;
spi[node] = S[ci].se;
}
else{
spi[node] = S[2].se;
}
for(auto x : R[node]){
if((id[x] == id[node] || ci == 1) && spi[x] == 0){
do_sp(x, ci);
}
}
}
vector<pii> C[N];
int sz[N];
vector<int> idi;
bool hvi[N];
int tot;
int curn;
int central;
bool has_sol;
void dfs2(int u){
hvi[u]=true;
idi.push_back(u);
tot += sz[u];
for(auto x : C[u]){
if(hvi[x.fi]) continue;
if(has_sol) return ;
if(tot + sz[x.fi] >= S[0].fi){
for(auto f : idi){
do_sp(nds[f][0], 0);
}
do_sp(x.se, 0);
do_sp(central, 1);
has_sol = true;
return ;
}
dfs2(x.fi);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
curn = n;
int m = p.size();
S[0] = mp(a, 1);
S[1] = mp(b, 2);
S[2] = mp(c, 3);
sort(S, S + 3);
spi.resize(n);
for(int i = 0 ; i < m ; i ++ ){
T[p[i]].push_back(q[i]);
T[q[i]].push_back(p[i]);
}
dfs(0);
int node = 0;
int pp = -1;
bool ok = true;
while(ok){
ok = false;
for(auto x : R[node]){
if(x != pp && subt[x] > n/2){
pp = node;
node = x;
ok = true;
break;
}
}
}
central = node;
for(int i = 0 ; i < n; i ++ ){
id[i] = -1;
}
id[node] = 0;
for(auto x : R[node]){
cnt ++ ;
dfs1(x, cnt);
}
for(auto x : R[node]){
if(sub[x] >= S[0].fi){
do_sp(x, 0);
do_sp(node, 1);
for(int i = 0; i < n; i ++ ){
if(spi[i] == 0) spi[i] = 3;
}
return spi;
}
sz[id[x]] = sub[x];
}
for(int i = 0 ;i < m ; i ++ ){
if(id[p[i]] == 0 || id[q[i]] == 0 || id[p[i]] == id[q[i]]) continue;
C[id[p[i]]].push_back(mp(id[q[i]], q[i]));
C[id[q[i]]].push_back(mp(id[p[i]], p[i]));
}
for(int i = 1; i <= cnt; i ++ ){
if(hvi[i]) continue;
tot = 0;
idi.clear();
dfs2(i);
if(has_sol){
for(int j = 0 ; j < n; j ++ ){
if(spi[j] == 0) spi[j] = S[2].se;
}
return spi;
}
}
return spi;
}
