#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 200005
vector<int> adj[MAXN];
vector<int> child[MAXN];
int res[MAXN], vis[MAXN], vis2[MAXN], sz[MAXN], P[MAXN], deg[MAXN];
void color(int node, int &cnt, int c){
if (cnt <= 0) return;
//cout<<node<<sp<<c<<endl;
res[node] = c;
cnt--;
for (auto i : child[node]){
color(i, cnt, c);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
for (int i = 0; i < p.size(); i++)
adj[p[i]].pb(q[i]), adj[q[i]].pb(p[i]), deg[p[i]]++, deg[q[i]]++;
for (int i = 0; i < n; i++)
sz[i] = 1;
vector<pii> v = {{a, 1}, {b, 2}, {c, 3}};
sort(v.rbegin(), v.rend());
priority_queue<pii> Q;
for (int i = 0; i < n; i++) if (adj[i].size() == 1) Q.push({-1, i});
vector<int> todo;
int root = -1;
int last = -1;
while(!Q.empty()){
int top = Q.top().nd;
Q.pop();
last = top;
for (auto i : adj[top]){
if (vis2[i]) continue;
P[top] = i;
}
if (sz[top] >= v.back().st && root == -1){
root = top;
}
else{
child[P[top]].pb(top);
sz[P[top]] += sz[top];
}
deg[P[top]]--;
vis2[top] = 1;
if (deg[P[top]] == 1)
Q.push({-sz[P[top]], P[top]});
}
vector<int> ans(n, 0);
if (root == -1 || n - sz[root] < v[1].st) return ans;
for (int i = 0; i < n; i++) res[i] = v[0].nd;
color(root, v[2].st, v[2].nd);
color(last, v[1].st, v[1].nd);
for (int i = 0; i < n; i++) ans[i] = res[i];
return ans;
}
