#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define f0r(i, n) for (auto i = 0; i < (n); ++i)
#define all(v) (v).begin(), (v).end()
#define F first
#define S second
using vi = vector<int>;
using pi = pair<int, int>;
#include "split.h"
vi res, sz, head, to, nxt;
int re;
void dfs(int v, int p) {
if (v == re) return;
sz[v] = 1;
for (int e = head[v]; ~e; e = nxt[e]) {
int c = to[e];
if (c != p) {
dfs(c, v);
sz[v] += sz[c];
}
}
}
void get_res(int v, int p, int &rem, int lbl) {
if (v == re || !rem) return;
res[v] = lbl;
rem--;
for (int e = head[v]; ~e; e = nxt[e]) {
int c = to[e];
if (c != p) get_res(c, v, rem, lbl);
}
}
vi find_split(int n, int a, int b, int c, vi p, vi q) {
res.assign(n, 0);
sz.assign(n, 0);
head.assign(n, -1);
int m = p.size();
to.resize(m * 2);
nxt.resize(m * 2);
f0r(i, m) {
to[i << 1] = q[i]; nxt[i << 1] = head[p[i]]; head[p[i]] = i << 1;
to[i << 1 | 1] = p[i]; nxt[i << 1 | 1] = head[q[i]]; head[q[i]] = i << 1 | 1;
}
vector<pi> lab{{a, 1}, {b, 2}, {c, 3}};
sort(all(lab));
f0r(i, 2) {
swap(lab[0], lab[1]);
res.assign(n, 0);
sz.assign(n, 0);
re = -1;
dfs(0, -1);
pi best = {2e9, 2e9};
f0r(j, n) if (sz[j] >= lab[1].F) best = min(best, {sz[j], j});
if (best.F == 2e9) continue;
int rem = lab[1].F;
get_res(best.S, -1, rem, lab[1].S);
re = best.S;
sz.assign(n, 0);
dfs(0, -1);
best = {2e9, 2e9};
f0r(j, n) if (sz[j] >= lab[0].F) best = min(best, {sz[j], j});
if (best.F == 2e9) continue;
rem = lab[0].F;
get_res(best.S, -1, rem, lab[0].S);
f0r(j, n) if (!res[j]) res[j] = lab[2].S;
return res;
}
return vi(n);
}
