#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define x first
#define y second
ll N, M, A, B, C;
vector<ll> G[100005];
vector<ll> T[100005];
ll visited[100005];
vector<int> ans;
ll idx[100005];
ll par[100005];
ll sz[100005];
vector<pair<ll, ll>> I;
struct UnionFind{
vector<ll> p;
UnionFind(ll S){
p.resize(S + 5, -1);
}
ll Find(ll n){
if (p[n] < 0) return n;
else return p[n] = Find(p[n]);
}
void Union(ll a, ll b){
a = Find(a), b = Find(b);
if (a == b) return;
p[a] += p[b];
p[b] = a;
}
bool Same(ll a, ll b) { return Find(a) == Find(b); }
ll Size(ll n) { return -p[Find(n)]; }
void Clear() {fill(p.begin(), p.end(), -1);}
};
ll getSize(ll u, ll p){
sz[u] = 1;
for(auto v : T[u]) if(v != p) sz[u] += getSize(v, u);
return sz[u];
}
ll getCent(ll u, ll p, ll c){
for(auto v : T[u]) if(v != p && sz[v] * 2 > c) return getCent(v, u, c);
return u;
}
ll num = 0;
void dfs(ll u){
num--;
if(num < 0) return;
ans[u] = I[1].y;
for(auto v : G[u]){
if(ans[v] != 0) continue;
dfs(v);
}
}
void dfs2(ll u, ll p, ll r){
num--;
if(num < 0) return;
ans[u] = I[0].y;
for(auto v : T[u]){
if(v == p || v == r) continue;
dfs2(v, u, r);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n, M = p.size(), A = a, B = b, C = c;
ans.resize(N);
I.push_back({A,1});I.push_back({B,2});I.push_back({C,3});
sort(I.begin(),I.end());
A=I[0].x,B=I[1].x,C=I[2].x;
UnionFind uf(N);
vector<pair<ll, ll>> MST, E;
for(int i = 0; i < M; i++){
ll u = p[i], v = q[i];
G[u].push_back(v);
G[v].push_back(u);
if(uf.Same(u, v)){
E.push_back({u, v});
continue;
}
uf.Union(u, v);
MST.push_back({u, v});
T[u].push_back(v);
T[v].push_back(u);
}
uf.Clear();
getSize(0, -1);
ll R = getCent(0, -1, N);
getSize(R, -1);
for(int i = 0; i < MST.size(); i++){
ll u = MST[i].x, v = MST[i].y;
if(u == R || v == R) continue;
uf.Union(u, v);
}
ll ok = 0;
ll NU = -1;
for(int i = 0; i < N; i++){
if(i == R) continue;
if(sz[i] >= A) ok = 1, NU = i;
}
ll ok2 = 0;
if(!ok){
for(int i = 0; i < E.size(); i++){
ll u = E[i].x, v = E[i].y;
if(u == R || v == R) continue;
uf.Union(u, v);
if(uf.Size(u) >= A){
NU = u;
break;
}
}
}
if(NU == -1){
return vector<int>(N, 0);
}
num = A;
dfs2(NU, -1, R);
num = B;
dfs(R);
assert(num <= 0);
for(int i = 0; i < N; i++){
if(ans[i] == 0){
ans[i] = I[2].y;
}
}
return ans;
}
