#include "split.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 100'010;
vector<int> A[N], At[N];
mt19937_64 rd(time(0));
bool vis[N];
int a, b, c;
int tag[3] = {1, 2, 3};
int n;
void sort_abc()
{
if (a > b) {
swap(a, b);
swap(tag[0], tag[1]);
}
if (b > c) {
swap(b, c);
swap(tag[1], tag[2]);
}
if (a > b) {
swap(a, b);
swap(tag[0], tag[1]);
}
}
void dfs2(int v, int p, vector<int> &vec)
{
vec.push_back(v);
for (int u : At[v])
if (u != p)
dfs2(u, v, vec);
}
vector<int> make_ans(vector<int> A, vector<int> B)
{
vector<int> ans(n, tag[2]);
for (int v : A)
ans[v] = tag[0];
for (int v : B)
ans[v] = tag[1];
return ans;
}
int sz[N];
void dfs0(int v)
{
sz[v] = 1;
vis[v] = 1;
for (int u : A[v]) {
if (!vis[u]) {
At[v].push_back(u);
At[u].push_back(v);
dfs0(u);
sz[v] += sz[u];
}
}
}
pii dfs1(int v, int p)
{
for (int u : At[v])
if (u != p && sz[u] >= a)
return dfs1(u, v);
if (n-sz[v] >= a)
return {v, p};
return {-1, -1};
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
n = _n; a = _a; b = _b; c = _c;
sort_abc();
Loop (i,0,p.size()) {
A[p[i]].push_back(q[i]);
A[q[i]].push_back(p[i]);
}
while (clock() < 1.8 * CLOCKS_PER_SEC) {
Loop (i,0,n) {
shuffle(A[i].begin(), A[i].end(), rd);
At[i].clear();
}
memset(vis, 0, sizeof(vis));
int rt = rd()%n;
dfs0(rt);
auto [x, y] = dfs1(rt, -1);
if (x == -1)
continue;
vector<int> A, B;
dfs2(x, y, A);
dfs2(y, x, B);
if (A.size() > B.size())
A.swap(B);
assert(A.size() >= a);
assert(B.size() >= b);
A.resize(a);
B.resize(b);
return make_ans(A, B);
}
return vector<int>(n, 0);
}
