#include <bits/stdc++.h>
#include "split.h"
using namespace std;
const int MN = 1e5+5;
vector<int> adj[MN];
int sz[MN], ohp[MN], p[MN]; bool vis[MN];
int dfs (int cur) {
vis[cur] = 1;
for (int i : adj[cur]) if (!vis[i]) {
ohp[i] = cur;
sz[cur] += dfs(i);
}
return ++sz[cur];
}
int getcent (int cur, int tot) {
for (int i : adj[cur]) if (ohp[i] == cur && sz[i] > (tot >> 1))
return getcent(i,tot);
return cur;
}
int calc (int cur) {
vis[cur] = sz[cur] = 1;
for (int i : adj[cur]) if ((ohp[i] == cur || ohp[cur] == i) && !vis[i]) {
p[i] = cur;
sz[cur] += calc(i);
}
return sz[cur];
}
vector<int> find_split (int n, int a, int b, int c, vector<int> P, vector<int> Q) {
vector<pair<int,int>> vv = {{a,1},{b,2},{c,3}};
sort(vv.begin(),vv.end());
vector<int> ret(n,vv[2].second);
a = vv[0].first; b = vv[1].first; c = vv[2].first;
for (int i = 0; i < (int)P.size(); i++) {
adj[++P[i]].push_back(++Q[i]);
adj[Q[i]].push_back(P[i]);
}
auto fillB = [&] (int st, int go, int put) {
queue<int> q; q.push(st); ret[st-1] = put; --go;
while (!q.empty()) {
int cur = q.front(); q.pop();
for (int i : adj[cur]) if (ret[i-1] == vv[2].second) {
q.push(i);
if (go) --go, ret[i-1] = put;
else return;
}
}
};
int cent = getcent(1,dfs(1)); memset(vis,0,sizeof vis);
calc(cent);
for (int i : adj[cent]) if (p[i] == cent && sz[i] >= a) {
queue<int> q; q.push(i);
while (a--) {
int cur = q.front(); q.pop(); ret[cur-1] = vv[0].second;
for (int j : adj[cur]) if (p[j] == cur) q.push(j);
}
fillB(cent,b,vv[1].second);
return ret;
}
vector<vector<int>> ree; vector<int> cnt,in;
for (int i : adj[cent]) if (p[i] == cent) {
in.push_back((int)ree.size()); ree.push_back({i}); cnt.push_back(sz[i]);
}
for (int i = 0; i < (int)P.size(); i++) if (p[P[i]] != Q[i] && p[Q[i]] != P[i] && in[P[i]] != in[Q[i]]) {
int u = in[P[i]], v = in[Q[i]];
if (cnt[u] > cnt[v]) swap(u,v);
cnt[v] += cnt[u];
for (int j : ree[u]) {in[j] = v; ree[v].push_back(j);}
}
for (int i = 0; i < (int)ree.size(); i++) if (cnt[i] >= a) {
while (cnt[i] - sz[ree[i].back()] >= a) {
ree[i].pop_back(); cnt[i] -= sz[ree[i].back()];
}
for (int j : ree[i]) {
queue<int> q; q.push(j);
while (a && !q.empty()) {
int cur = q.front(); q.pop(); --a; ret[cur-1] = vv[0].second;
for (int k : adj[cur]) if (p[k] == cur) q.push(k);
}
}
fillB(cent,b,vv[1].second);
return ret;
}
fill(ret.begin(),ret.end(),0);
return ret;
}
