#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct UnionFind {
int par[N], sz[N];
void init() {
iota(par, par + N, 0);
fill_n(sz, N, 1);
}
int find(int x) { return par[x] = x == par[x] ? x : find(par[x]); }
void unite(int a, int b) {
a = find(a), b = find(b);
if(a == b) return;
par[a] = b, sz[b] += sz[a];
}
int size(int a) { return sz[find(a)]; }
} dsu;
int sub[N];
vector<int> g[N];
int dfs(int u, int p) {
sub[u] = 1;
for(int v : g[u]) if(v != p)
sub[u] += dfs(v, u);
return sub[u];
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int ida = 1, idb = 2, idc = 3;
if(a > b) swap(a, b), swap(ida, idb);
if(a > c) swap(a, c), swap(ida, idc);
if(b > c) swap(b, c), swap(idb, idc);
dsu.init();
for(int i = 0; i < p.size(); i++) if(dsu.find(p[i]) != dsu.find(q[i])) {
g[p[i]].emplace_back(q[i]);
g[q[i]].emplace_back(p[i]);
dsu.unite(p[i], q[i]);
}
int rot = -1;
function<int(int)> find_rot = [&](int u) {
int p = u;
while(1) {
int mx = -1, nex = -1;
for(int v : g[u]) if(v != p && sub[v] > mx)
mx = sub[v], nex = v;
if(mx <= n - b) return u;
p = u, u = nex;
}
};
dfs(0, 0), rot = find_rot(0);
if(rot == -1) return vector<int>(n);
//cerr << "rot = " << rot << endl;
dsu.init();
for(int i = 0; i < p.size(); i++) {
if(p[i] == rot || q[i] == rot) continue;
dsu.unite(p[i], q[i]);
}
for(int i = 0; i < p.size(); i++) {
if(dsu.find(p[i]) == dsu.find(q[i])) continue;
if(p[i] == rot || q[i] == rot) continue;
if(dsu.size(p[i]) >= a || dsu.size(q[i]) >= a) continue;
dsu.unite(p[i], q[i]);
g[p[i]].emplace_back(q[i]);
g[q[i]].emplace_back(p[i]);
}
vector<int> ans(n);
function<void(int, int, int&, int)> flood = [&](int u, int col, int &cnt, int block) {
if(ans[u] || cnt == 0 || u == block) return;
ans[u] = col, --cnt;
//cerr << "flooding " << u << " " << col << endl;
for(int v : g[u]) flood(v, col, cnt, block);
};
for(int i = 0; i < n; i++) if(i != rot && dsu.size(i) >= a) {
flood(i, ida, a, rot), flood(rot, idb, b, -1);
for(int &x: ans) if(!x) x = idc;
break;
}
return ans;
}
