#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 2;
vector<pair<int,int> > color;
vector<int> adj[maxn],adjTree[maxn],sack[maxn],res;
bool vis[maxn];
int N,M,A,B,C,subSize[maxn],par[maxn],centroid;
void dfsTree(int u){
bool isCentroid = true;
vis[u] = true;
subSize[u] = 1;
for(int v : adj[u]){
if(!vis[v]){
dfsTree(v);
subSize[u] += subSize[v];
if(subSize[v] > N/2){
isCentroid = false;
}
adjTree[u].push_back(v);
adjTree[v].push_back(u);
}
}
if(isCentroid && N-subSize[u] <= N/2){
centroid = u;
}
}
void dfsLow(int u,int c){
if(A == 0) return;
res[u] = c;
A--;
for(int v : adj[u]){
if(par[v] == par[u] && !res[v]){
dfsLow(v,c);
}
}
}
void dfsMid(int u,int c){
if(B == 0) return;
res[u] = c;
B--;
for(int v : adj[u]){
if(!res[v]){
dfsMid(v,c);
}
}
}
vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q){
N = n,M = p.size();
for(int i=0;i<M;i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
for(int i=0;i<N;i++){
par[i] = i;
sack[i].push_back(i);
}
color = {{a,1},{b,2},{c,3}};
sort(color.begin(),color.end());
A = color[0].first,B = color[1].first,C = color[2].first;
res = vector<int>(N);
dfsTree(0);
for(int i=0;i<N;i++){
if(i != centroid){
for(int j : adjTree[i]){
if(j != centroid){
if(sack[par[i]].size() > sack[par[j]].size()){
for(int it : sack[par[j]]){
par[it] = par[i];
sack[par[i]].push_back(it);
}
}else{
for(int it : sack[par[i]]){
par[it] = par[j];
sack[par[j]].push_back(it);
}
}
}
}
if(sack[par[i]].size() >= A){
dfsLow(par[i],color[0].second);
dfsMid(centroid,color[1].second);
for(int &it : res) if(!it) it = color[2].second;
return res;
}
}
}
for(int i=0;i<N;i++){
if(i != centroid){
for(int j : adj[i]){
if(j != centroid && par[i] != par[j]){
if(sack[par[i]].size() > sack[par[j]].size()){
for(int it : sack[par[j]]){
par[it] = par[i];
sack[par[i]].push_back(it);
}
}else{
for(int it : sack[par[i]]){
par[it] = par[j];
sack[par[j]].push_back(it);
}
}
}
}
if(sack[par[i]].size() >= A){
dfsLow(par[i],color[0].second);
dfsMid(centroid,color[1].second);
for(int &it : res) if(!it) it = color[2].second;
return res;
}
}
}
return res;
}
