#include "split.h"
#include <functional>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <deque>
using namespace std;
vector<int> find_split(int n, int oA, int oB, int oC, vector<int> p, vector<int> q) {
int m = (int) p.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; ++i) {
adj[p[i]].push_back(i);
adj[q[i]].push_back(i);
}
vector<int> inTree(m, 0), vis(n, 0), par(n, -1), sz(n, 0);
function<int(int)> findCentroid = [&](int u) -> int {
vis[u] = true, sz[u] = 1;
int cen = -1;
for (int i : adj[u]) {
int v = u ^ p[i] ^ q[i];
if (vis[v]) continue;
inTree[i] = true;
int can = findCentroid(v);
if (cen == -1) cen = can;
sz[u] += sz[v];
}
if (cen == -1 && 2 * sz[u] >= n) cen = u;
return cen;
};
int root = findCentroid(0);
array<int, 3> arr = {oA, oB, oC};
int a = *min_element(arr.begin(), arr.end()), c = *max_element(arr.begin(), arr.end()), b = n - a - c;
vector<int> ans(n, 0);
fill(vis.begin(), vis.end(), 0);
vector<int> done(n, 0);
done[root] = 1;
for (int ir : adj[root]) if (inTree[ir]) {
int u = root ^ p[ir] ^ q[ir];
if (done[u]) continue;
vector<int> vec;
deque<int> dq = {u};
while (!dq.empty()) {
int v = dq.front();
dq.pop_front();
if (done[v]) continue;
done[v] = true;
vec.push_back(v);
for (int i : adj[v]) {
int w = v ^ p[i] ^ q[i];
if (done[w]) continue;
if (inTree[i]) {
if (vis[w] < 2) {
dq.push_front(w);
vis[w] = 2;
}
} else {
if (vis[w] < 1) {
dq.push_back(w);
vis[w] = 1;
}
}
}
}
if ((int) vec.size() >= a) {
vec.resize(a);
for (auto v : vec) ans[v] = 1;
break;
}
}
if (count(ans.begin(), ans.end(), 1) != a) return ans;
vis = ans;
vector<int> vec = {root};
vis[root] = true;
for (int iv = 0; iv < (int) vec.size(); ++iv) {
int u = vec[iv];
for (int i : adj[u]) {
int v = u ^ p[i] ^ q[i];
if (vis[v]) continue;
vis[v] = true;
vec.push_back(v);
}
}
assert((int) vec.size() >= b);
vec.resize(b);
for (int v : vec) ans[v] = 2;
array<int, 3> idx = {0, 1, 2};
sort(idx.begin(), idx.end(), [&](int i, int j) { return arr[i] < arr[j]; });
for (int &x : ans) {
if (x == 0) x = idx[2] + 1;
else if (x == 1) x = idx[0] + 1;
else x = idx[1] + 1;
}
return ans;
}
