#include "split.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N = (int)3e5;
vector<int> g[N];
int sz[N];
bool used[N];
int p[N];
mt19937 rnd(time(nullptr));
void dfs (int v){
sz[v] = 1;
used[v] = true;
for(auto& to : g[v]){
if(used[to]) continue;
p[to] = v;
dfs(to);
sz[v] += sz[to];
}
return;
};
std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q){
bool group1 = true;
int m = p.size();
for(int i = 0; i < m; i++){
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
for(int i = 0; i < n; i++){
group1 &= (g[i].size() <= 2);
}
if(group1){
int root = 0;
for(int i = 0; i < n; i++){
if(g[i].size() == 1)
root = i;
}
queue<int> q;
q.push(root);
bool used[n];
memset(used,0,sizeof used);
vector<int> order;
while(!q.empty()){
int v = q.front();
q.pop();
used[v] = true;
order.push_back(v);
for(auto& to : g[v]){
if(!used[to]){
used[to] = true;
q.push(to);
}
}
}
vector<int> ans(n);
for(int i = 0; i < a; i++){
ans[order[i]] = 1;
}
for(int i = a; i < a+b; i++){
ans[order[i]] = 2;
}
for(int i = a+b; i < a+b+c; i++){
ans[order[i]] = 3;
}
return ans;
}
if(a == 1){
bool used[n];
memset(used,0,sizeof used);
bool deleted = false;
vector<int> ans(n);
for(int i = 0; i < n; i++){
if(g[i].size() == 1){
deleted = true;
used[i] = true;
ans[i] = 1;
break;
}
}
if(!deleted){
used[0] = true;
ans[0] = 1;
deleted = true;
}
int root = 0;
if(used[root]) root++;
queue<int> q;
q.push(root);
vector<int> order;
while(!q.empty()){
int v = q.front();
q.pop();
used[v] = true;
order.push_back(v);
for(auto& to : g[v]){
if(!used[to]){
used[to] = true;
q.push(to);
}
}
}
for(int i = 0; i < b; i++){
ans[order[i]] = 2;
}
for(int i = b; i < b+c; i++){
ans[order[i]] = 3;
}
return ans;
}
if(m == n-1){
int val[3] = {1,2,3};
if(a > b){
swap(a,b);
swap(val[0],val[1]);
}
if(b > c){
swap(b,c);
swap(val[1],val[2]);
}
if(a > b){
swap(a,b);
swap(val[0],val[1]);
}
memset(used,0,sizeof used);
memset(sz,0,sizeof sz);
int root = 0;
for(int i = 0; i < n; i++){
if(g[i].size() > 1)
root = i;
}
// root = rnd()%n;
p[root] = -1;
dfs(root);
memset(used,0,sizeof used);
vector<int> ans(n,0);
for(int i = 0; i < n; i++){
if(sz[i] >= a && n - sz[i] >= b){
queue<int> q;
q.push(i);
used[i] = true;
ans[i] = val[0];
a--;
while(!q.empty()){
int v = q.front();
q.pop();
used[v] = true;
ans[v] = val[0];
for(auto& to : g[v]){
if(to == p[v] || a == 0) continue;
q.push(to);
a--;
}
}
q.push(p[i]);
used[p[i]] = true;
ans[p[i]] = val[1];
b--;
while(!q.empty()){
int v = q.front();
q.pop();
used[v] = true;
ans[v] = val[1];
for(auto& to : g[v]){
if(used[to] || b == 0) continue;
q.push(to);
b--;
}
}
for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = val[2];
return ans;
}
if(sz[i] >= b && n - sz[i] >= a){
queue<int> q;
q.push(i);
used[i] = true;
ans[i] = val[1];
b--;
while(!q.empty() && b > 0){
int v = q.front();
q.pop();
used[v] = true;
ans[v] = val[1];
for(auto& to : g[v]){
if(to == p[v]) continue;
q.push(to);
b--;
}
}
q.push(p[i]);
used[p[i]] = true;
ans[p[i]] = val[0];
a--;
while(!q.empty() && a > 0){
int v = q.front();
q.pop();
used[v] = true;
ans[v] = val[0];
for(auto& to : g[v]){
if(used[to]) continue;
q.push(to);
a--;
}
}
for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = val[2];
return ans;
}
}
return ans;
}
return vector<int>(n,0);
}
