#include <bits/stdc++.h>
#include "split.h"
using namespace std;
const int N = 2e5 + 5;
vector<int> graph[N], ans;
int n, a, b, c;
void fill_ans(int v, int bad, int cnt, int typ){
vector<bool> vis(n, false);
int curcnt = 1;
queue<int> que;
que.push(v), vis[v] = true;
while(!que.empty() && curcnt < cnt){
v = que.front(); que.pop();
for(auto e : graph[v]){
if(!vis[e] && e != bad){
vis[e] = true;
que.push(e);
curcnt++;
if(curcnt == cnt) break;
}
}
}
for(int i = 0; i < n; i++) if(vis[i]) ans[i] = typ;
}
bool flag = false;
int dfs(int v, int p){
if(flag) return 0;
int cnt = 1;
for(auto e : graph[v]){
if(e != p) cnt += dfs(e, v);
}
if(flag) return 0;
if(cnt >= a){
if(n - cnt >= b){
fill_ans(v, p, a, 1);
fill_ans(p, v, b, 2);
for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = 3;
flag = true;
return 0;
}
else if(n - cnt >= c){
fill_ans(v, p, a, 1);
fill_ans(p, v, c, 3);
for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = 2;
flag = true;
return 0;
}
}
if(cnt >= b){
if(n - cnt >= a){
fill_ans(v, p, b, 2);
fill_ans(p, v, a, 1);
for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = 3;
flag = true;
return 0;
}
else if(n - cnt >= c){
fill_ans(v, p, b, 2);
fill_ans(p, v, c, 3);
for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = 1;
flag = true;
return 0;
}
}
if(cnt >= c){
if(n - cnt >= a){
fill_ans(v, p, c, 3);
fill_ans(p, v, a, 1);
for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = 2;
flag = true;
return 0;
}
else if(n - cnt >= b){
fill_ans(v, p, c, 3);
fill_ans(p, v, b, 2);
for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = 1;
flag = true;
return 0;
}
}
return cnt;
}
vector<int> find_split(int n_, int a_, int b_, int c_, vector<int> p, vector<int> q){
n = n_, a = a_, b = b_, c = c_;
int m = p.size();
ans.assign(n, 0);
for(int i = 0; i < m; i++){
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
if(a == 1){ // Subtask 2
fill_ans(0, -1, b, 2);
for(int i = 0; i < n; i++){
if(ans[i] == 0){
ans[i] = 1;
break;
}
}
for(int i = 0; i < n; i++){
if(ans[i] == 0){
ans[i] = 3;
}
}
}
else if(m == n - 1){ // Subtask 3
dfs(0, -1);
}
else{ // Subtask 1
graph[p[m - 1]].pop_back();
graph[q[m - 1]].pop_back();
dfs(0, -1);
}
return ans;
}
