#include <bits/stdc++.h>
#include "split.h"
using namespace std;
constexpr size_t N = 100000;
vector<int> g[N], t[N], color;
int n, a, b, h[N], l[N], s[N], label[3];
bitset<N> visited;
void build_dfs_tree(int u)
{
visited[u] = 1;
l[u] = h[u];
s[u] = 1;
for (auto const &v : g[u])
if (!visited[v])
{
h[v] = h[u] + 1;
t[u].push_back(v);
build_dfs_tree(v);
l[u] = min(l[u], l[v]);
s[u] += s[v];
}
else
l[u] = min(l[u], h[v]);
}
void label_component(int u, int size, int l)
{
queue<int> q({u});
while (size--)
{
int x = q.front();
q.pop();
color[x] = l;
for (auto const &v : t[u])
q.push(v);
}
}
bool dfs(int u, int p = -1)
{
visited[u] = 1;
for (auto const &v : g[u])
if (!visited[v])
if (dfs(v, u))
return 1;
if (s[u] >= a)
{
if (p == -1)
return 1;
t[p].erase(find(t[p].begin(), t[p].end(), u));
int y = s[u];
for (size_t i = 0; i < t[u].size(); ++i)
{
int v = t[u][i];
if (l[v] < h[u])
{
if (y - s[v] < a)
break; // We know the graph outside u's subtree is >= b
y -= s[v];
swap(t[u][i], t[u].back());
t[u].pop_back();
t[0].push_back(v);
}
}
if (n - y >= b)
{
label_component(u, a, label[0]);
label_component(0, b, label[1]);
for (int &x : color)
if (!x)
x = label[2];
}
else if (y >= b)
{
label_component(u, b, label[1]);
label_component(0, a, label[0]);
for (int &x : color)
if (!x)
x = label[2];
}
return 1;
}
return 0;
}
vector<int> find_split(int n_, int a_, int b_, int c, vector<int> p, vector<int> q)
{
int const sizes[3] = {a_, b_, c};
label[0] = 1, label[1] = 2, label[2] = 3;
sort(label, label + 3, [&](auto const &i, auto const &j)
{ return sizes[i - 1] < sizes[j - 1]; });
n = n_, a = sizes[label[0] - 1], b = sizes[label[1] - 1];
for (size_t i = 0; i < p.size(); ++i)
g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]);
build_dfs_tree(0);
visited.reset();
color.resize(n);
dfs(0);
return color;
}
