#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> draw;
{// a < b < c
vector<pair<int,int>> need{{a,1},{b,2},{c,3}};
sort(need.begin(),need.end());
a = need[0].first,b = need[1].first,c = need[2].first;
draw = {need[0].second,need[1].second,need[2].second};
}
vector<vector<int>> edges(N);
vector<int> color(N,draw[2]);
for(int i = 0;i < p.size();i++){
edges[p[i]].push_back(q[i]);
edges[q[i]].push_back(p[i]);
}
vector<vector<int>> child(N);
vector<int> sz(N,1);
function<void(int,int)> dfs = [&](int cur,int par){
for(auto nxt:edges[cur]){
if(nxt == par) continue;
child[cur].push_back(nxt);
dfs(nxt,cur);
}
};
function<int(int)> set_sz = [&](int cur){
for(auto nxt:child[cur]){
sz[cur] += set_sz(nxt);
}
return sz[cur];
};
dfs(0,-1);
set_sz(0);
int root = -1;
int s1,s2;
function<void(int,int)> set_color1 = [&](int cur,int changeto){
if(s1 > 0){
color[cur] = changeto;
s1--;
}
for(auto nxt:child[cur]){
set_color1(nxt,changeto);
}
};
function<void(int,int)> set_color2 = [&](int cur,int changeto){
if(s2 > 0){
color[cur] = changeto;
s2--;
}
for(auto nxt:child[cur]){
if(nxt == root) continue;
set_color2(nxt,changeto);
}
};
for(int i = 0;i < N;i++){
if(sz[i] >= a && N-sz[i] >= b) {
root = i;
s1 = a,s2 = b;
set_color1(i,draw[0]);
set_color2(0,draw[1]);
return color;
}
if(sz[i] >= b && N-sz[i] >= a) {
s1 = b,s2 = a;
set_color1(i,draw[1]);
set_color2(0,draw[0]);
root = i;
return color;
}
}
return vector<int>(N,0);
}
