#include "split.h"
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
typedef int ll;
#define MAX 101010
ll N;
ll num[MAX], prt[MAX];
ll color[MAX];
vector<ll> adj[MAX], tree[MAX];
ll vis[MAX];
ll cnt = 0;
ll ord[MAX];
ll memo[MAX];
ll arr[MAX];
ll split[2][MAX];
ll dfs(ll x = 0, ll p = -1) {
ord[x] = ++cnt;
prt[x] = p;
num[x] = 1;
vis[x] = 1;
ll ret = ord[x];
for (auto v : adj[x]) {
if (v == p) continue;
if (vis[v]) {
ret = min(ret, ord[v]);
continue;
}
ret = min(dfs(v, x), ret);
num[x] += num[v];
}
return memo[x] = ret;
}
void chk(ll x, ll p, ll c) {
arr[x] = c;
for (auto v : tree[x]) {
if (v == p) continue;
chk(v, x, c);
}
}
void dfs2(ll x, ll p, ll c) {
split[c][x] = ++cnt;
vis[x] = 1;
for (auto v : adj[x]) {
if (v == p || arr[v] != c) continue;
if (vis[v]) continue;
dfs2(v, x, c);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> res;
N = n;
res.resize(N);
ll i;
for (i = 0; i < q.size(); i++) adj[p[i]].push_back(q[i]), adj[q[i]].push_back(p[i]);
dfs();
for (i = 0; i < N; i++) vis[i] = 0;
ll s[3] = { a, b, c };
ll pp[3] = { 0, 0, 0 };
pp[(s[0] > s[1] ? 0 : 1)]++;
pp[(s[1] > s[2] ? 1 : 2)]++;
pp[(s[0] > s[2] ? 0 : 2)]++;
ll m = s[pp[0]];
ll asdf[3];
asdf[pp[0]] = 0;
asdf[pp[1]] = 1;
asdf[pp[2]] = 2;
pp[0] = asdf[0];
pp[1] = asdf[1];
pp[2] = asdf[2];
for (i = 1; i < N; i++) {
tree[i].push_back(prt[i]);
tree[prt[i]].push_back(i);
}
c = 0;
while (1) {
ll ccc = 1;
for (auto v : tree[c]) {
if (v == prt[c]) continue;
if (num[v] >= m) {
ccc = 0, c = v;
break;
}
}
if (ccc) break;
}
ll nc = num[c];
vector<ll> sav;
chk(0, -1, 1);
chk(c, prt[c], 0);
for (auto v : tree[c]) {
if (v == prt[c]) continue;
if (memo[v] >= ord[v]) continue;
if (nc - num[v] < m) break;
if (N - nc >= s[pp[1]]) break;
nc -= num[v];
sav.push_back(v);
}
if (!(nc >= s[pp[0]] && (N - nc) >= s[pp[1]])) {
sav.clear();
nc = num[c];
if (nc < s[pp[1]]) return res;
for (auto v : tree[c]) {
if (v == prt[c]) continue;
if (memo[v] >= ord[v]) continue;
if (nc - num[v] < s[pp[1]]) break;
if (N - nc >= s[pp[0]]) break;
nc -= num[v];
sav.push_back(v);
}
if (!(nc >= s[pp[1]] && (N - nc) >= s[pp[0]])) return res;
for (auto v : sav) chk(v, c, 1);
cnt = 0;
dfs2(0, -1, 1);
for (i = 0; i < N; i++) vis[i] = 0;
cnt = 0;
dfs2(c, prt[c], 0);
for (i = 0; i < N; i++) res[i] = pp[2] + 1;
for (i = 0; i < N; i++) {
if (!arr[i] && split[0][i] <= s[pp[1]]) {
res[i] = pp[1] + 1;
}
}
for (i = 0; i < N; i++) {
if (arr[i] && split[1][i] <= s[pp[0]]) {
res[i] = pp[0] + 1;
}
}
vector<ll> v(4);
for (i = 0; i < N; i++) {
v[res[i]]++;
}
//assert(s[p[0]] == v[1] && s[p[1]] == v[2]);
return res;
}
for (auto v : sav) chk(v, c, 1);
cnt = 0;
dfs2(0, -1, 1);
for (i = 0; i < N; i++) vis[i] = 0;
cnt = 0;
dfs2(c, prt[c], 0);
for (i = 0; i < N; i++) res[i] = pp[2] + 1;
for (i = 0; i < N; i++) {
if (!arr[i] && split[0][i] <= s[pp[0]]) {
res[i] = pp[0] + 1;
}
}
for (i = 0; i < N; i++) {
if (arr[i] && split[1][i] <= s[pp[1]]) {
res[i] = pp[1] + 1;
}
}
vector<ll> v(4);
for (i = 0; i < N; i++) {
v[res[i]]++;
}
//assert(s[p[0]] == v[1] && s[p[1]] == v[2]);
return res;
}
