#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 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)
{
///cout << v << endl;
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);
}
}
int cp_idx[maxn];
vector < int > a_list;
bool found = false;
int cur_sz;
void find_path(int v)
{
cur_sz += cp_list[v].size();
used[v] = 1;
a_list.push_back(v);
for (int u : tree[v])
{
if (cur_sz >= A)
{
found = true;
break;
}
if (used[u])
continue;
find_path(u);
}
}
int sp[maxn];
void fill_component_again(int v, int sz)
{
component.push_back(v);
used[v] = 1;
for (int u : tree[v])
{
if (component.size() == sz)
break;
if (used[u])
continue;
fill_component_again(u, 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]);
///cout << p[i] << " " << q[i] << endl;
}
}
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;
}
}
//cout << "here" << endl;
for (int i = 0; i < cp_list.size(); i ++)
{
for (int v : cp_list[i])
cp_idx[v] = i;
}
cp_idx[centroid] = -1;
for (int i = 0; i < n; i ++)
tree[i].clear();
for (int i = 0; i < m; i ++)
{
if (tree_edge[i])
continue;
if (cp_idx[p[i]] == cp_idx[q[i]])
continue;
if (p[i] == centroid || q[i] == centroid)
continue;
tree[cp_idx[p[i]]].push_back(cp_idx[q[i]]);
tree[cp_idx[q[i]]].push_back(cp_idx[p[i]]);
}
vector < int > res(n, 0);
memset(used, 0, sizeof(used));
for (int i = 0; i < cp_list.size() && !found; i ++)
{
a_list.clear();
cur_sz = 0;
find_path(i);
}
if (!found)
return res;
for (int i = 0; i < n; i ++)
tree[i].clear();
int sum = 0;
for (int i = 0; i < a_list.size(); i ++)
sum += cp_list[a_list[i]].size();
for (int i = 0; i < a_list.size(); i ++)
for (int v : cp_list[a_list[i]])
sp[v] = 1;
for (int i = 0; i < m; i ++)
{
if (sp[p[i]] == sp[q[i]])
{
tree[p[i]].push_back(q[i]);
tree[q[i]].push_back(p[i]);
}
}
component.clear();
int root1 = 0;
while(sp[root1] == 0)
root1 ++;
int root2 = 0;
while(sp[root2] == 1)
root2 ++;
fill_component_again(root1, A);
for (int v : component)
res[v] = type[1];
component.clear();
fill_component_again(root2, B);
for (int v : component)
res[v] = type[2];
for (int i = 0; i < n; i ++)
if (res[i] == 0)
res[i] = type[3];
return res;
}
