#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int N, A;
vector<vector<int>> g;
vector<int> num, low;
int dfs_cnt = 0;
bool possible = false;
vector<bool> comp;
void revisit(int u){
comp[u] = true;
for(int v : g[u]){
if(!comp[v] && num[v] > num[u]) revisit(v);
}
}
int dfs(int u, int par){
num[u] = low[u] = dfs_cnt++;
vector<pair<int, int>> must, can;
int max_subtree = 0;
for(int v : g[u]){
if(v == par) continue;
if(num[v] == -1){
int size = dfs(v, u);
max_subtree = max(max_subtree, size);
if(size == -1) return -1; // answer already found
low[u] = min(low[u], low[v]);
if(num[u] <= low[v]) must.emplace_back(size, v);
else can.emplace_back(size, v);
}
else low[u] = min(low[u], num[v]);
}
int min_size = 1, max_size = 1;
for(auto [s, v] : must) min_size += s, max_size += s;
for(auto [s, v] : can) max_size += s;
if(min_size <= N-A && max_size >= A && max_subtree < A){
int size = min_size;
possible = true;
comp[u] = true;
for(auto [s, v] : must) revisit(v);
for(auto [s, v] : can){
if(size >= A) break;
size += s;
revisit(v);
}
return -1;
}
return max_size;
}
vector<pair<int, int>> bySize;
vector<int> ans;
vector<bool> vis;
int cnt = 0, cur;
void dfs2(int u){
vis[u] = true;
if(cnt < bySize[cur].first){
cnt++;
ans[u] = bySize[cur].second;
}
else ans[u] = bySize[2].second;
for(int v : g[u]){
if(!vis[v] && comp[u] == comp[v]){
dfs2(v);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
bySize = {{a, 1}, {b, 2}, {c, 3}};
sort(bySize.begin(), bySize.end());
g.resize(n);
for(int i = 0; i < (int)p.size(); i++){
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
N = n;
A = bySize[0].first;
num.assign(n, -1);
low.resize(n);
comp.resize(n);
dfs(0, -1);
if(!possible) return vector<int>(n, 0);
else{
ans.resize(n);
int cn = 0;
for(int i = 0; i < n; i++) cn += comp[i];
if(cn < n/2) swap(bySize[0], bySize[1]);
for(int i = 0; i < 2; i++){
cur = i; cnt = 0;
vis.assign(n, false);
for(int u = 0; u < n; u++){
if(comp[u] == i){
dfs2(u);
break;
}
}
}
return ans;
}
}
