#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
const int MAX_N=2510;
vector<vi> G;
vector<ii> ab;
vector<int> res;
int n,m;
int num[MAX_N],low[MAX_N],pa[MAX_N],art[MAX_N],sb[MAX_N];
int vis[MAX_N];
int ite=0;
void dfs(int u,int p){
sb[u]=1;
pa[u]=p;
low[u]=num[u]=ite; ite++;
vis[u]=1;
for(auto &v:G[u]){
if(!vis[v]){
dfs(v,u);
sb[u]+=sb[v];
low[u]=min(low[u],low[v]);
}
else{
if(v!=p)
low[u]=min(low[u],num[v]);
}
}
}
vector<int> ba,na;
int dp[MAX_N][MAX_N];
int path[MAX_N][MAX_N];
int dif,tam;
int knap(int id,int w){
if(dp[id][w]!=-1) return dp[id][w];
if(id==ba.size()){
if(w<dif) return 1e9;
return w;
}
int to=knap(id+1,w+ba[id]);
int nt=knap(id+1,w);
path[id][w]=(to<nt);
return dp[id][w]=min(to,nt);
}
void colorear(int u,int col,bool sw){
if(tam==0) return;
res[u]=col;
tam--;
for(auto &v:G[u]){
if((sw || num[u]<num[v]) && !res[v]){
colorear(v,col,sw);
}
if(tam==0) return;
}
}
vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
memset(vis,0,sizeof vis);
n=nn;
m=p.size();
G.resize(n+1);
res.resize(n);
for(int i=0;i<m;i++){
int a=p[i],b=q[i];
G[a].push_back(b);
G[b].push_back(a);
}
ab={ii(a,1),ii(b,2),ii(c,3)};
sort(ab.begin(),ab.end());
dfs(0,0);
for(int i=0;i<n;i++){
if(sb[i]<ab[0].first) continue;
int br=1;
ba.clear();
na.clear();
for(auto &v:G[i]){
if(pa[i]==v) continue;
if(low[v]>num[i]){
br+=sb[v];
}
else{
ba.push_back(sb[v]);
na.push_back(v);
}
}
vector<int> to,nt;
int id;
if(br<a){
dif=a-br;
for(int j=0;j<=ba.size();j++) for(int k=0;k<=dif;k++) dp[j][k]=-1;
knap(0,0);
id=0;
int w=0;
while(id!=ba.size()){
if(path[id][w]){
to.push_back(na[id]);
w+=ba[id];
}
else nt.push_back(na[id]);
id++;
}
}
else nt=na;
id=0;
int o1,o2;
o1=-1; o2=sb[0]-sb[i];
int ot;
for(int j=0;j<nt.size();j++){
if(low[nt[j]]<num[i]) o2+=sb[nt[j]];
if(o1<sb[nt[j]]) ot=nt[j];
o1=max(o1,sb[nt[j]]);
}
if(o1<o2) ot=pa[i];
int re=max(o1,o2);
if(re>=ab[1].first){
res[i]=ab[0].second;
tam=ab[0].first-1;
for(auto &v:G[i]){
if(pa[i]!=v && low[v]>num[i]){
colorear(v,ab[0].second,0);
}
}
for(int j=0;j<to.size();j++){
colorear(to[j],ab[0].second,0);
}
tam=ab[1].first;
colorear(ot,ab[1].second,1);
for(int j=0;j<res.size();j++){
if(res[j]==0) res[j]=ab[2].second;
}
break;
}
}
return res;
}
