#include "split.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
namespace{
vector<int> ord;
vector<int> sz, pa;
vector<vector<int>> graph;
void dfs(int node, int parent){
sz[node] = 1;
pa[node] = parent;
ord.push_back(node);
for(auto &x: graph[node]){
if(x == parent) continue;
dfs(x, node);
sz[node] += sz[x];
}
}
void dfs_ban(int node, int parent, int ban){
ord.push_back(node);
for(auto &x: graph[node]){
if(x == parent || x == ban) continue;
dfs_ban(x, node, ban);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> ans(n);
sz.resize(n);
graph.resize(n);
pa.resize(n);
for(int i = 0; i < n - 1; i++){
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
dfs(0, 0);
if(a == 1){
for(int i = 0; i < b; i++) ans[ord[i]] = 2;
for(int i = b; i < b + c; i++) ans[ord[i]] = 3;
ans[ord[n - 1]] = 1;
return ans;
}
int na = 1, nb = 2, nc = 3;
if(a > b){
swap(a, b);
swap(na, nb);
}
if(b > c){
swap(b, c);
swap(nb, nc);
}
if(a > b){
swap(a, b);
swap(na, nb);
}
vector<int> old = ord, pos(n);
for(int i = 0; i < n; i++) pos[ord[i]] = i;
vector<int>().swap(ord);
for(int i = 0; i < n; i++){
if(sz[i] >= a && n - sz[i] >= b){
dfs_ban(pa[i], pa[i], i);
for(int j = pos[i]; j < pos[i] + a; j++) ans[old[j]] = na;
for(int j = 0; j < b; j++) ans[ord[j]] = nb;
for(int j = 0; j < n; j++) if(ans[j] == 0) ans[j] = nc;
return ans;
}
if(sz[i] >= b && n - sz[i] >= a){
dfs_ban(pa[i], pa[i], i);
for(int j = pos[i]; j < pos[i] + b; j++) ans[old[j]] = nb;
for(int j = 0; j < a; j++) ans[ord[j]] = na;
for(int j = 0; j < n; j++) if(ans[j] == 0) ans[j] = nc;
return ans;
}
}
return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run split.cpp grader.cpp
