#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, m, k, id[N], siz[N], rt;
vector<int> adj[N], tadj[N], nadj[N], comps[N], orda;
vector<pair<int, int>> bruh;
bool vis[N];
void get_tree(int v){
vis[v] = 1; siz[v] = 1;
for(auto u : adj[v])
if(!vis[u]) tadj[v].push_back(u), tadj[u].push_back(v), get_tree(u), siz[v] += siz[u];
}
int get_centroid(){
int p = -1, v = 0;
do{
int nxt = -1;
for(auto u : tadj[v])
if(u!=p && 2*siz[u]>n) nxt = u;
p = v, v = nxt;
} while(~v);
return p;
}
void get_label(int v, int p, int idx){
comps[idx].push_back(v);
id[v] = idx;
for(auto u : tadj[v])
if(u!=p) get_label(u, v, idx);
}
void get_orda(int v){
vis[v] = 1;
orda.push_back(v);
for(auto u : adj[v])
if(!vis[u]) get_orda(u);
}
vector<int> get_ans(vector<int> a0){
memset(vis, 0, sizeof vis);
for(auto x : a0) vis[x] = 1;
for(int i = 0; i<n; ++i)
if(!vis[i]){get_orda(i); break;}
vector<int> ans(n, bruh[2].second);
while((int)a0.size()>bruh[0].first) orda.push_back(a0.back()), a0.pop_back();
for(auto x : a0)
ans[x] = bruh[0].second;
for(int i = 0; i<bruh[1].first; ++i)
ans[orda[i]] = bruh[1].second;
return ans;
}
bool find_good(int v, int& cur){
vis[v] = 1; cur += comps[v].size();
orda.push_back(v);
if(cur>=bruh[0].first) return 1;
for(auto u : nadj[v])
if(!vis[v]) if(find_good(u, cur)) return 1;
return 0;
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> _p, vector<int> _q){
n = _n, m = _p.size();
bruh.push_back({_a, 1});
bruh.push_back({_b, 2});
bruh.push_back({_c, 3});
sort(bruh.begin(), bruh.end());
for(int i = 0; i<m; ++i)
adj[_p[i]].push_back(_q[i]), adj[_q[i]].push_back(_p[i]);
get_tree(0);
rt = get_centroid(); k = tadj[rt].size();
for(int i = 0; i<k; ++i)
get_label(tadj[rt][i], rt, i);
id[rt] = -1; siz[rt] = n;
for(int i = 0; i<k; ++i)
if((int)comps[i].size()>=bruh[0].first)
return get_ans(comps[i]);
for(int i = 0; i<m; ++i){
int u = id[_p[i]], v = id[_q[i]];
if(u==v || u==-1 || v==-1) continue;
nadj[u].push_back(v);
nadj[v].push_back(u);
} memset(vis, 0, sizeof vis);
for(int i = 0; i<k; ++i){
if(vis[i]) continue;
int tot = 0;
if(find_good(i, tot)){
vector<int> a0;
for(auto x : orda)
a0.insert(a0.end(), comps[x].begin(), comps[x].end());
orda.clear(); return get_ans(a0);
}
}
vector<int> ans(n, 0);
return ans;
}
