#include "split.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int NMAX = 1e6 + 1;
int sz[NMAX], p[NMAX];
vector <vector <int> > g(NMAX);
vector <vector <int> > G(NMAX);
vector <bool> used(NMAX);
set <pii> edges;
set <pii> tree;
int t[NMAX];
int mx[NMAX];
void dfs(int v, int e = -1){
used[v] = true;
t[v] = 1;
for(int to : g[v]){
if(used[to]) continue;
edges.erase({to, v});
edges.erase({v, to});
tree.insert({v, to});
G[v].pb(to);
dfs(to);
t[v] += t[to];
mx[v] = max(mx[v], t[to]);
}
}
int find_cen(int v, int n){
if(2 * (n - t[v]) <= n){
if(mx[v] * 2 <= n) return v;
}
for(int to : G[v]) {
int x = find_cen(to, n);
if(x) return x;
}
return 0;
}
void make_set(int v){
p[v] = v;
sz[v] = 1;
}
int find_set(int v){
return (v == p[v]) ? v : p[v] = find_set(p[v]);
}
void union_sets(int a, int b){
a = find_set(a);
b = find_set(b);
if(a == b) return ;
if(sz[a] < sz[b])swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
vector <int> ans;
int cnt = 0;
void getcmp(int v, int x, int a){
cnt++;
ans[v] = x;
used[v] = true;
if(cnt == a){
return;
}
for(int to : G[v]){
if(used[to]) continue;
getcmp(to, x, a);
if(cnt == a) return;
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
for(int i = 0; i < p.size(); i++){
int u = p[i], v = q[i];
g[u].pb(v);
g[v].pb(u);
edges.insert({u, v});
}
dfs(0);
int x = find_cen(0, n);
for(int i = 0; i < n; i++){
make_set(i);
}
for(auto to : tree){
if(to.f != x && to.s != x) union_sets(to.f, to.s);
}
vector <pii> vec;
vec.pb({a, 1});
vec.pb({b, 2});
vec.pb({c, 3});
sort(vec.begin(), vec.end());
ans.resize(n);
for(int i = 0; i < n; i++){
ans[i] = vec[2].s;
}
bool ind = false;
for(int i = 0; i < n; i++){
if(i == x) continue;
int xx = find_set(i);
if(sz[xx] >= vec[0].f){
for(int j = 0; j < n; j++) used[j] = false;
used[x] = true;
getcmp(xx, vec[0].s, vec[0].f);
used[x] = false;
cnt = 0;
getcmp(x, vec[1].s, vec[1].f);
ind = true;
break;
}
}
if(!ind){
for(auto to : edges){
int u = to.f, v = to.s;
union_sets(u, v);
u = find_set(u);
G[v].pb(u);
G[u].pb(v);
if(sz[u] >= vec[0].f){
for(int j= 0; j < n; j++){
used[j] = false;
}
used[x] = true;
getcmp(u, vec[0].s, vec[0].f);
cnt = 0;
used[x] = false;
getcmp(x, vec[1].s, vec[1].f);
ind = true;
break;
}
}
}
if(!ind) {
ans.assign(n, 0);
return ans;
}
return ans;
}
