#include <bits/stdc++.h>
#define pb push_back
#include "split.h"
//#define DEBUGGING
using namespace std;
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
constexpr static int MXN = 1e5;
array<array<int, 2>, 3> arr;
vector<array<int, 2>> g[MXN];
vector<int> res;
set<int> used;
int subsize[MXN];
bitset<MXN> visited;
int n;
struct Node
{
int head, tail, size, nxt;
Node(int i) : head(i), tail(i), size(1), nxt(-1) {}
Node() : Node(-1) {}
};
Node node[MXN];
void merge(int a, int b)
{
if (node[a].size < node[b].size) swap(a,b);
node[a].size += node[b].size;
node[node[a].tail].nxt = b;
node[a].tail = node[b].tail;
for (; b != -1; b = node[b].nxt)
node[b].head = a;
}
void dfs1(int node)
{
subsize[node] = 1;
for (auto [c, index] : g[node])
{
if (!subsize[c])
{
dfs1(c);
subsize[node] += subsize[c];
}
}
}
int find_centroid(int i)
{
for (auto [c,index]: g[i])
if (subsize[c] < subsize[i] && subsize[c] >= (n/2))
return find_centroid(c);
return i;
}
void dfs2(int i)
{
for (auto [c, index] : g[i])
{
if (subsize[c] < subsize[i])
{
used.insert(index);
assert(node[c].head != node[i].head);
merge(node[c].head, node[i].head);
dfs2(c);
}
}
}
void dfs3(int i)
{
visited[i] = true;
for (auto [c, index] : g[i])
{
if (!visited[c])
{
debug(i, c);
used.insert(index);
assert(node[c].head != node[i].head);
merge(node[c].head, node[i].head);
dfs3(c);
}
}
}
int centroid;
int counter;
bool dfs4(int i, int val)
{
res[i] = arr[val][1];
counter++;
if (counter == arr[val][0])
return true;
for (auto [c, index] : g[i])
{
if (node[c].head == node[i].head && !res[c])
{
bool out = dfs4(c, val);
if (out)
return true;
}
}
return false;
}
bool dfs5(int i, int val)
{
res[i] = arr[val][1];
counter++;
if (counter == arr[val][0])
return true;
for (auto [c, index] : g[i])
{
if (!res[c])
{
bool out = dfs5(c, val);
if (out)
return true;
}
}
return false;
}
vector<int> finish(int subtree)
{
int val = 0;
if (node[subtree].size >= arr[1][0])
val = 1;
assert(dfs4(subtree, val));
counter = 0;
assert(dfs5(centroid, val^1));
for (int i = 0; i < n; i++)
if (!res[i])
res[i] = arr[2][1];
return res;
}
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 < n; i++)
node[i] = Node(i);
arr[0] = {a, 1};
arr[1] = {b, 2};
arr[2] = {c, 3};
sort(arr.begin(), arr.end());
for (int i = 0; i < p.size(); i++)
{
g[p[i]].pb({q[i], i});
g[q[i]].pb({p[i], i});
}
dfs1(0);
centroid = find_centroid(0);
visited[centroid] = true;
debug(centroid);
for (auto [c, index] : g[centroid])
{
used.insert(index);
if (subsize[c] < subsize[centroid])
dfs2(c);
}
for (auto [c, index] : g[centroid])
if (subsize[c] > subsize[centroid])
dfs3(c);
for (auto [c, index] : g[centroid])
if ((subsize[c] < subsize[centroid] && subsize[c] >= arr[0][0]) || (subsize[c] > subsize[centroid] && subsize[c] - subsize[centroid] >= arr[0][0]))
return finish(node[c].head);
for (int i = 0; i < p.size(); i++)
{
if (used.find(i) != used.end() || p[i] == centroid || q[i] == centroid)
continue;
used.insert(i);
if (node[p[i]].head == node[q[i]].head)
continue;
merge(node[p[i]].head, node[q[i]].head);
if (node[node[p[i]].head].size >= arr[0][0])
return finish(node[p[i]].head);
}
return res;
}
