#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
struct edge
{
int v, u;
edge(int _v = 0, int _u = 0)
{
v = _v;
u = _u;
}
}e[maxn];
int deg[maxn], m, n, A, B, C, type[4];
vector < pair < int, int > > graph[maxn];
int used[maxn], tree_edge[maxn];
vector < int > order;
void dfs(int v)
{
used[v] = 1;
for (pair < int, int > nb : graph[v])
{
if (used[nb.first] == 1)
continue;
tree_edge[nb.second] = 1;
dfs(nb.first);
}
}
vector < int > tree[maxn];
int sub[maxn];
void calc(int v, int p)
{
sub[v] = 1;
for (int u : tree[v])
{
if (u == p)
continue;
calc(u, v);
sub[v] += sub[u];
}
}
int find_centroid(int v, int p)
{
for (int u : tree[v])
{
if (u == p)
continue;
if (sub[u] >= n / 2)
return find_centroid(u, v);
}
return v;
}
vector < vector < int > > cp_list;
vector < int > component;
void trav(int v, int p)
{
component.push_back(v);
for (int u : tree[v])
{
if (u == p)
continue;
trav(u, v);
}
}
void fill_component(int v, int p, int sz)
{
component.push_back(v);
for (int u : tree[v])
{
if (component.size() == sz)
break;
if (u == p)
continue;
fill_component(u, v, sz);
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q)
{
n = N;
m = p.size();
for (int i = 0; i < p.size(); i ++)
{
graph[p[i]].push_back({q[i], i});
graph[q[i]].push_back({p[i], i});
}
for (int i = 0; i < m; i ++)
{
e[i] = edge(p[i], q[i]);
}
dfs(0);
for (int i = 0; i < m; i ++)
{
if (tree_edge[i])
{
tree[p[i]].push_back(q[i]);
tree[q[i]].push_back(p[i]);
}
}
calc(0, -1);
int centroid = find_centroid(0, -1);
memset(used, 0, sizeof(used));
for (int u : tree[centroid])
{
component.clear();
trav(u, centroid);
cp_list.push_back(component);
}
A = a;
B = b;
C = c;
type[1] = 1;
type[2] = 2;
type[3] = 3;
if (A > B)
{
swap(A, B);
swap(type[1], type[2]);
}
if (A > C)
{
swap(A, C);
swap(type[1], type[3]);
}
if (B > C)
{
swap(B, C);
swap(type[2], type[3]);
}
for (int i = 0; i < cp_list.size(); i ++)
{
if (cp_list[i].size() >= A)
{
vector < int > res(n, 0);
component.clear();
fill_component(cp_list[i][0], centroid, A);
for (int v : component)
res[v] = type[1];
component.clear();
fill_component(centroid, cp_list[i][0], B);
for (int v : component)
res[v] = type[2];
for (int j = 0; j < n; j ++)
if (res[j] == 0)
res[j] = type[3];
return res;
}
}
vector < int > res(n, 0);
return res;
}
