#include<bits/stdc++.h>
#include "split.h"
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 1e5 ;
bool us[N + 1] ;
int vert, sz[N + 1], ind[N + 1] ;
vector<int> ts, res, v[N + 1], other[N + 1], tree[N + 1] ;
void ultra_clear()
{
for(int i = 0 ; i < N ; i++)
us[i] = 0 ;
}
void build_tree(int city)
{
us[city] = 1 ;
for(int i : v[city])
{
if(us[i])
continue ;
tree[city].push_back(i) ;
build_tree(i) ;
}
}
void dfs_for_tree(int city, int a1)
{
ind[city] = ts.size() ;
ts.push_back(city) ;
sz[city]++ ;
int mx = 0 ;
for(int i : tree[city])
{
dfs_for_tree(i, a1) ;
mx = max(mx, sz[i]) ;
sz[city] += sz[i] ;
}
if(mx < a1 && sz[city] >= a1)
vert = city ;
}
void dfs_color(int city, int &cnt, int color)
{
us[city] = 1 ;
if(cnt)
{
cnt-- ;
res[city] = color ;
}
for(int i : tree[city])
{
if(us[i])
continue ;
dfs_color(i, cnt, color) ;
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> fr, vector<int> to)
{
vector<pair<int, int>> all = {{a, 1}, {b, 2}, {c, 3}} ;
sort(all.begin(), all.end()) ;
int m = fr.size() ;
for(int i = 0 ; i < n ; i++)
res.push_back(0) ;
for(int i = 0 ; i < m ; i++)
{
v[fr[i]].push_back(to[i]) ;
v[to[i]].push_back(fr[i]) ;
}
build_tree(0) ;
dfs_for_tree(0, all[0].fi) ;
for(int i = 0 ; i < m ; i++)
{
int f = fr[i], t = to[i] ;
if(ind[vert] <= ind[f] && ind[f] < ind[vert] + sz[vert] && ind[t] < ind[vert])
other[f].push_back(t) ;
if(ind[vert] <= ind[t] && ind[t] < ind[vert] + sz[vert] && ind[f] < ind[vert])
other[t].push_back(f) ;
}
vector<int> del ;
for(int i = ind[vert] + 1 ; i < ind[vert] + sz[vert] ; i++)
{
int now = ts[i] ;
if(sz[vert] - sz[now] >= all[0].fi && other[now].size())
{
del.push_back(now) ;
tree[other[now][0]].push_back(now) ;
us[now] = 1 ;
sz[vert] -= sz[now] ;
i = ind[now] + sz[now] - 1 ;
}
}
if(sz[vert] >= all[0].fi && n - sz[vert] >= all[1].fi)
{
ultra_clear() ;
dfs_color(vert, all[0].fi, all[0].se) ;
for(int i : del)
us[i] = 0 ;
dfs_color(0, all[1].fi, all[1].se) ;
for(int i = 0 ; i < n ; i++)
if(!res[i])
res[i] = all[2].se ;
}
return res ;
}
//signed main()
//{
// ios_base::sync_with_stdio( 0 ) ;
// cin.tie( 0 ) ;
// cout.tie( 0 ) ;
// int n, m, a, b, c ;
// cin >> n >> a >> b >> c >> m ;
// vector<int> fr(m), to(m) ;
// for(int i = 0 ; i < m ; i++)
// cin >> fr[i] >> to[i] ;
// vector<int> ans = find_split(n, a, b, c, fr, to) ;
// for(int i : ans)
// cout << i << ' ' ;
// return 0 ;
//}
