#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
// #define int long long
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
vector<int> find_split(int n, int A, int B, int C, vector<int> p, vector<int> q) {
int m = q.size();
vector<vector<int>> g(n);
for(int i = 0; i < m; i++) {
g[p[i]].pb(q[i]);
g[q[i]].pb(p[i]);
}
vector<vector<int>> ret(3);
vector<int> tmp, a(3), vis(n);
tmp.pb(A); tmp.pb(B); tmp.pb(C);
for(int i = 0; i < 3; i++) {
a[i] = i;
}
sort(all(a), [&](int x, int y) {
return tmp[x] < tmp[y];
});
auto bfs = [&](int st, int sz) -> vector<int> {
queue<int> q;
q.push(st);
vis[st] = 1;
vector<int> ret;
ret.pb(st);
while(q.size() && (int)ret.size() < sz) {
int x = q.front(); q.pop();
for(int y : g[x]) {
if(vis[y] || (int)ret.size() == sz) continue;
vis[y] = 1;
ret.pb(y);
q.push(y);
}
}
return ret;
};
if(m == n - 1) {
vector<int> S(n, 1), P(n);
function<void(int, int)> dfs = [&](int to, int fr) -> void {
P[to] = fr;
for(int x : g[to]) {
if(x ==fr) continue;
dfs(x, to);
S[to] += S[x];
}
};
dfs(0, -1);
for(int i = 0; i < n; i++) {
if((S[i] >= tmp[a[0]] && n - S[i] >= tmp[a[1]]) || (S[i] >= tmp[a[1]] && n - S[i] >= tmp[a[0]])) {
g[i].erase(find(all(g[i]), P[i]));
g[P[i]].erase(find(all(g[i]), i));
if(S[i] >= tmp[a[0]] && n - S[i] >= tmp[a[1]]) {
ret[a[0]] = bfs(i, tmp[a[0]]);
ret[a[1]] = bfs(P[i], tmp[a[1]]);
} else {
ret[a[1]] = bfs(i, tmp[a[1]]);
ret[a[0]] = bfs(P[i], tmp[a[0]]);
}
for(int j = 0; j < n; j++) {
if(vis[j] == 0) ret[a[2]].pb(j);
}
vector<int> ans(n);
for(int j = 0; j < 3; j++) {
for(int x : ret[j]) {
ans[x] = j + 1;
}
}
return ans;
}
}
return vector<int>(n, 0);
}
ret[a[1]] = bfs(0, tmp[a[1]]);
for(int i = 0; i < n; i++) {
if(!vis[i]) {
ret[a[0]] = bfs(i, tmp[a[0]]);
break;
}
}
for(int i = 0; i < n; i++) {
if(!vis[i]) {
ret[a[2]].pb(i);
}
}
vector<int> ans(n);
for(int j = 0; j < 3; j++) {
for(int x : ret[j]) {
ans[x] = j + 1;
}
}
return ans;
}
