#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) begin(x), end(x)
const int mx = 100005;
int n, a, b, c;
vi L;
bool SUB1 = 1;
bool SUB2 = 1;
bool SUB3 = 1;
bool SUB4 = 1;
vi adj[mx];
vi res;
int sub[mx];
int par[mx];
vi children[mx];
void genSub(int node, int prv = -1){
sub[node] = 1;
for(auto u: adj[node]){
if(u == prv) continue;
children[node].pb(u);
par[u] = node;
genSub(u, node);
sub[node]+=sub[u];
}
}
int cnt;
void makeSub(int node, int num, int id){
if(num != -1){
cnt = num;
makeSub(node, -1, id);
return;
}
if(cnt == 0) return;
res[node] = id;
cnt--;
for(auto u: children[node]) makeSub(u, -1, id);
}
void makenSub(int node, int num, int id, int prv = -1){
//cout << node << " " << num << " " << id << " " << prv << "\n";
if(num != -1){
cnt = num;
makenSub(node, -1, id, prv);
return;
}
if(cnt == 0) return;
res[node] = id;
cnt--;
if(node != 0 && par[node] != prv) makenSub(par[node], -1, id, node);
for(auto u: children[node]) if(u != prv) makenSub(u, -1, id, node);
}
bool visited[mx];
vi comp;
void getComp(int node){
if(visited[node]) return;
visited[node] = 1;
comp.pb(node);
for(auto u: adj[node]){
getComp(u);
}
}
int tcount;
void assign2(int node){
if(tcount >= L[1]) return;
if(res[node] != 0) return;
res[node] = 2;
tcount++;
for(auto u: adj[node]){
assign2(u);
}
}
void adjustRes(){
vi to(4, 0);
vpi cnt;
cnt.pb(mp(a, 1)); cnt.pb(mp(b, 2)); cnt.pb(mp(c, 3));
sort(all(cnt));
for(int i = 0; i < 3; i++) to[i+1] = cnt[i].s;
for(auto &u: res) u = to[u];
}
void search(int node){
//cout << "node: " << node << "\n";
visited[node] = 1;
vi good;
for(auto u: adj[node]){
if(visited[u]) continue;
comp.clear();
getComp(u);
// cout << "u: " << u << "\n";
// for(auto u: comp) cout << u << " ";
// cout << "\n";
if(sz(comp) < L[0]){
}
else{
//cout << "SOLFOUND\n";
if(n-sz(comp) >= L[1]){
//solution found!
for(int i = 0; i < n; i++){
res[i] = 0;
}
int ocount = 0;
for(auto u: comp){
if(ocount < L[0]){
ocount++;
res[u] = 1;
}
else res[u] = -1;
}
for(auto u: res) if(u == 0){
tcount = 0;
assign2(u);
break;
}
for(int i = 0; i < sz(res); i++){
if(res[i] != 1 && res[i] != 2) res[i] = 3;
}
return;
}
good = comp;
}
}
for(auto u: good){
visited[u] = 0;
}
for(auto u: adj[node]){
if(visited[u]) continue;
search(u);
return;
}
}
vi find_split(int _n, int _a, int _b, int _c, vi p, vi q) {
n = _n;
a = _a;
b = _b;
c = _c;
L.pb(a);
L.pb(b);
L.pb(c);
sort(all(L));
res = vi(n, 0);
for(int i = 0; i < sz(p); i++){
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
for(int i = 0; i < n; i++){
if(sz(adj[i]) > 2) SUB1 = 0;
}
if(a != 1) SUB2 = 0;
if(sz(p) != n-1) SUB3 = 0;
if(n > 2500 || sz(p) > 5000) SUB4 = 0;
// if(SUB1){
// int A = 0;
// int B = 0;
// int C = 0;
// int cur = 0;
// for(int i = 0; i < n; i++) if(sz(adj[i]) == 1) cur = i;
// int last = -1;
// while(true){
// if(A < a){
// res[cur] = 1;
// A++;
// }
// else if(B < b){
// res[cur] = 2;
// B++;
// }
// else if(C < c){
// res[cur] = 3;
// C++;
// }
// else break;
// if(adj[cur][0] == last){
// if(sz(adj[cur]) == 1) break;
// last = cur;
// cur = adj[cur][1];
// }
// else{
// last = cur;
// cur = adj[cur][0];
// }
// }
// return res;
// }
// if(SUB2){
// vi inComp(n, 0);
// queue<int> q;
// int B = 0;
// inComp[0] = 1;
// B++;
// q.push(0);
// while(sz(q)){
// int node = q.front();
// q.pop();
// for(auto u: adj[node]) if(inComp[u] == 0 && B < b){
// inComp[u] = 1;
// B++;
// q.push(u);
// }
// if(B == b) break;
// }
// for(int i = 0; i < n; i++) if(inComp[i] == 1) res[i] = 2;
// for(int i = 0; i < n; i++){
// if(inComp[i] == 0){
// res[i] = 1;
// break;
// }
// }
// for(int i = 0; i < n; i++) if(res[i] == 0) res[i] = 3;
// return res;
// }
// if(SUB3){
// genSub(0);
// for(int i = 0; i < n; i++){
// if(a <= sub[i] && min(b, c) <= n-sub[i]){
// //cout << i << "1\n";
// makeSub(i, a, 1);
// if(b <= c){
// makenSub(par[i], b, 2, i);
// }
// else{
// makenSub(par[i], c, 3, i);
// }
// break;
// }
// if(b <= sub[i] && min(a, c) <= n-sub[i]){
// //cout << i << "2\n";
// makeSub(i, b, 2);
// if(a <= c){
// makenSub(par[i], a, 1, i);
// }
// else{
// makenSub(par[i], c, 3, i);
// }
// break;
// }
// if(c <= sub[i] && min(a, b) <= n-sub[i]){
// //cout << i << "3\n";
// makeSub(i, c, 3);
// if(a <= b){
// makenSub(par[i], a, 1, i);
// }
// else{
// makenSub(par[i], b, 2, i);
// }
// break;
// }
// }
// vi full(4, 0);
// for(int i = 0; i < n; i++) full[res[i]] = 1;
// if(full[1] == 0 && full[2] == 0 && full[3] == 0){
// return res;
// }
// for(int i = 1; i <= 3; i++) if(full[i] == 0){
// for(int j = 0; j < n; j++){
// if(res[j] == 0) res[j] = i;
// }
// }
// return res;
// }
if(SUB4){
search(0);
int onecount = 0;
for(auto u: res) if(u == 1) onecount++;
if(onecount != L[0]){
return vi(n, 0);
}
adjustRes();
return res;
}
return res;
}
