#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];
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];
}
}
}
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) return;
else{
res[s - 1] = cock;
A--;
for(auto it : nod_MST[s]){
if(it != par && !res[it]) dfs_vanilla(it, s, cock);
}
}
}
void construct(int it){
viz.reset();
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;
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n; M = p.size();
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;
dfs(centroid);
for(auto it : nod_MST[centroid]){
if(sz[it] >= a){
construct(it);
return res;
}
}
}
