#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
const int inf = 1e9;
pair<int,int> v[3];
vector <int> e[N];
int dpth[N], low[N], vis[N], pr[N], sub[N];
vector <int> res;
vector <int> c;
bool add[N];
int n;
void dfs(int node, int p, int d){
dpth[node] = d;
low[node] = d;
vis[node] = 1;
pr[node] = p;
sub[node] = 1;
for(auto i:e[node]){
if(i == p)continue;
if(!vis[i]){
dfs(i, node, d + 1);
sub[node]+=sub[i];
low[node] = min(low[node], low[i]);
}else{
low[node] = min(low[node], dpth[i]);
}
}
}
void assignsubtree(int node, int id){
res[node] = id;
for(auto i:e[node]){
if(pr[i] == node){
assignsubtree(i, id);
}
}
}
int cnt = 0;
void dfs2(int node, int id){
res[node] = id;cnt--;
if(cnt == 0)return;
for(auto i:e[node]){
if(cnt != 0 && res[i] == 0){
dfs2(i, id);
}
if(cnt == 0)return;
}
}
bool checkok(int node, int sz1, int sz2){
cout<<"check:"<<node<<' '<<sz1<<' '<<sz2<<'\n';
for(int j = 0;j < 2;j++){
if(sz1 >= v[j].first && sz2 >= v[j^1].first){
cnt = inf;
res[node] = v[j].second;
for(auto i:e[node]){
if(pr[i] == node && add[i]){
cout<<"add:"<<i<<' '<<v[j].second<<'\n';
assignsubtree(i, v[j].second);
}
}
cnt = v[j^1].first;
dfs2(pr[node], v[j^1].second);
return 1;
}
}
return 0;
}
bool check(int node){
for(auto i:e[node]){
if(pr[i] == node){
add[i] = 1;
}
}
int sz1 = sub[node], sz2 = n - sub[node];
if(checkok(node, sz1, sz2)){
return 1;
}
for(auto i:e[node]){
if(pr[i] == node && low[i] < dpth[node]){
sz1-=sub[i];
sz2+=sub[i];
add[i] = 0;
if(checkok(node, sz1, sz2)){
return 1;
}
}
}
return 0;
}
vector<int> find_split(int n2, int a, int b, int c, vector<int> p, vector<int> q) {
n = n2;
res.resize(n);
for(int i = 0;i < (int)p.size();i++){
e[p[i]].push_back(q[i]);
e[q[i]].push_back(p[i]);
}
v[0] = {a, 1};
v[1] = {b, 2};
v[2] = {c, 3};
sort(v, v + 3);
dfs(0, -1, 0);
bool ans = 0;
for(int i = 0;i < n;i++){
if(check(i)){
ans = 1;
break;
}
}
if(ans){
for(int i = 0;i < n;i++){
if(res[i] == 0)res[i] = v[2].second;
}
}
return res;
}
/**
9, 4, 2, 3, [0, 0, 0, 0, 0, 0, 1, 3, 4, 5],
[1, 2, 3, 4, 6, 8, 7, 7, 5, 6]
9 10 4 2 3
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6
**/
