// 40 points
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int N;
pair<int, int> g[3];
vector<vector<int>> adj;
vector<vector<pair<int, int>>> tree_adj;
vector<int> visited, sz, label;
void constructTree(int index)
{
for (auto node : adj[index])
{
if (visited[node]) continue;
visited[node] = 1;
tree_adj[index].push_back({0, node});
tree_adj[node].push_back({0, index});
constructTree(node);
}
}
int DFS(int index, int last)
{
sz[index] = 1;
for (auto&node:tree_adj[index])
{
if (node.second == last) continue;
node.first = DFS(node.second, index);
sz[index] += node.first;
}
for (auto&node : tree_adj[index])
{
if (node.second != last) continue;
node.first = N - sz[index];
break;
}
return sz[index];
}
int lbl_a = 0;
void labelA(int index, int last)
{
if (lbl_a < g[0].first)
label[index] = g[0].second;
else
label[index] = g[2].second;
lbl_a++;
for (auto node : tree_adj[index])
{
if (node.second == last) continue;
labelA(node.second, index);
}
}
int lbl_b = 0;
void labelB(int index, int last)
{
if (lbl_b < g[1].first)
label[index] = g[1].second;
else
label[index] = g[2].second;
lbl_b++;
for (auto node : tree_adj[index])
{
if (node.second == last) continue;
labelB(node.second, index);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
N = n;
const int M = p.size();
g[0] = {a, 1}; g[1] = {b, 2}; g[2] = {c, 3};
sort(g, g + 3);
adj = vector<vector<int>>(N);
for (int i = 0; i < M; i++)
{
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
for (int root = 0; root < N; root++)
{
// Construct DFS tree
tree_adj = vector<vector<pair<int, int>>>(N);
visited = vector<int>(N); visited[root] = 1;
constructTree(root);
sz = vector<int>(N);
DFS(root, root);
for (int i = 0; i < N; i++)
{
sort(tree_adj[i].begin(), tree_adj[i].end());
// Find the smallest subtree larger than g[0].first
if (tree_adj[i].back().first < g[0].first) continue;
int l = 0, r = tree_adj[i].size() - 1;
while (l < r)
{
int c = (l + r) / 2;
if (tree_adj[i][c].first < g[0].first)
l = c + 1;
else
r = c;
}
int subtree = tree_adj[i][l].first;
if (sz[i] - subtree < g[1].first) continue;
label = vector<int>(N);
labelA(tree_adj[i][l].second, i);
labelB(i, tree_adj[i][l].second);
return label;
}
}
return vector<int>(N);
}
