#include <bits/stdc++.h>
#define pb push_back
#include "split.h"
using namespace std;
constexpr static int MXN = 1e5;
vector<int> g[MXN];
int subsize[MXN], n;
vector<int> res;
array<array<int, 2>, 3> arr;
array<int, 3> counter;
void dfs2(int node, int parent, int val)
{
if (counter[val] == arr[val][0])
return;
counter[val]++;
res[node] = arr[val][1];
for (int c : g[node])
if (c != parent)
dfs2(c, node, val);
}
bool dfs1(int node, int parent)
{
subsize[node] = 1;
for (int c : g[node])
{
if (c != parent)
{
bool out = dfs1(c, node);
if (out)
return true;
subsize[node] += subsize[c];
}
}
if (subsize[node] >= arr[0][0] && n - subsize[node] >= arr[1][0])
{
dfs2(node, parent, 0);
dfs2(parent, node, 1);
return true;
}
else if (subsize[node] >= arr[1][0] && n - subsize[node] >= arr[0][0])
{
dfs2(node, parent, 1);
dfs2(parent, node, 0);
return true;
}
return false;
}
vector<int> rg[MXN];
bitset<MXN> visited;
void create_dfs_tree(int node, int parent)
{
visited[node] = true;
if (parent != -1)
{
g[node].pb(parent);
g[parent].pb(node);
}
for (int c : rg[node])
if (!visited[c])
create_dfs_tree(c, node);
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q)
{
n = _n;
res = vector<int>(n, 0);
for (int i = 0; i < p.size(); i++)
{
rg[p[i]].pb(q[i]);
rg[q[i]].pb(p[i]);
}
arr[0] = {a, 1};
arr[1] = {b, 2};
arr[2] = {c, 3};
sort(arr.begin(), arr.end());
if (n >= 2500)
{
create_dfs_tree(0, -1);
if (dfs1(0, -1))
for (int i = 0; i < n; i++)
if (!res[i])
res[i] = arr[2][1];
return res;
}
else
{
for (int j = 0; j < n; j++)
{
create_dfs_tree(j, -1);
if (dfs1(j, -1))
{
for (int i = 0; i < n; i++)
if (!res[i])
res[i] = arr[2][1];
return res;
}
}
}
return res;
}
