#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
//#define int long long
#define rc(s) return cout << s, 0
using namespace std;
const int nmax = 100005;
int N, M, A, B, C, sz[nmax], centroid, indx1, indx2, indx3;
vector<int> res, nod[nmax], nod_MST[nmax], O_o;
bitset<nmax>viz;
void dfs(int s){
viz[s] = 1; sz[s] = 1;
for(auto it : nod[s]){
if(!viz[it]){
nod_MST[s].push_back(it);
nod_MST[it].push_back(s);
dfs(it);
sz[s] += sz[it];
}
}
}
void dfs2(int s){
viz[s] = 1; sz[s] = 1;
for(auto it : nod_MST[s]){
if(!viz[it]){
dfs2(it);
sz[s] += sz[it];
}
}
}
int findcentroid(int s, int par = 0){
for(auto it : nod_MST[s]){
if(it != par && sz[it] > (N / 2)){
return findcentroid(it, s);
}
}
return s;
}
void dfs_vanilla(int s, int par, int cock){
if(A == 0) return;
else{
res[s - 1] = cock;
A--;
for(auto it : nod_MST[s]){
if(it != par && !res[it - 1]) dfs_vanilla(it, s, cock);
}
}
}
void construct(int it){
dfs_vanilla(it, centroid, indx1);
A = B;
dfs_vanilla(centroid, 0, indx2);
for(int i=0;i<N;i++){
if(!res[i]){
res[i] = indx3;
}
}
}
void dfs_finala(int s){
viz[s] = 1;
O_o.push_back(s);
for(auto it : nod[s]){
if(it != centroid && !viz[it]){
dfs_finala(it);
}
}
}
void dfs_slavic(int s, int par = 0){
if(!B){
return;
}
else{
--B;
res[s - 1] = indx2;
for(auto it : nod_MST[s]){
if(it != par && !viz[it]) dfs_slavic(it, s);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n; M = p.size();
for(auto &it : p){
++it;
}
for(auto &it : q){
++it;
}
vector<pair<int,int>>tz; tz.push_back({a, 1}); tz.push_back({b, 2}); tz.push_back({c, 3});
sort(all(tz));
A = tz[0].fr; B = tz[1].fr; C = tz[2].fr;
indx1 = tz[0].sc, indx2 = tz[1].sc, indx3 = tz[2].sc;
res.resize(N);
for(int i=0;i<M;i++){
nod[p[i]].push_back(q[i]);
nod[q[i]].push_back(p[i]);
}
dfs(1);
centroid = findcentroid(1);
viz.reset();
for(int i=1;i<=n;i++) sz[i] = 0;
dfs2(centroid);
for(auto it : nod_MST[centroid]){
if(sz[it] >= A){
construct(it);
return res;
}
}
viz.reset();
for(int i=1;i<=n;i++){
if(i != centroid){
O_o.clear();
dfs_finala(i);
if(O_o.size() >= a){
for(int i=0;i<a;i++) res[O_o[i] - 1] = indx1;
viz.reset();
for(auto it : O_o) viz[it] = 1;
dfs_slavic(centroid);
for(int i=0;i<n;i++){
if(!res[i]) res[i] = indx3;
}
return res;
}
}
}
return res;
}
