#include "split.h"
#include <algorithm>
using namespace std;
using vi = vector<int>;
const int MAXN = 1e5;
vi G[MAXN], CC[MAXN];
bool vis[MAXN];
void DFS(int current_node, int current_CC){
vis[current_node] = true;
CC[current_CC].push_back(current_node);
for(int v : G[current_node]){
if(!vis[v]) DFS(v, current_CC);
}
}
vector<int> find_split(int n, int a, int b, int c, vi p, vi q){
vi res(n, 0);
for(int i=0; i<(int)p.size(); i++){
G[p[i]].push_back(q[i]);
G[q[i]].push_back(p[i]);
}
int current_CC = 0;
for(int i=0; i<n; i++){
if(!vis[i]) { DFS(i, current_CC); current_CC++; }
}
pair<int,int> CC_info[current_CC], values[3] = { {a, 1}, {b, 2}, {c, 3} };
for(int i=0; i<current_CC; i++) { CC_info[i].first = CC[i].size(); CC_info[i].second = i; }
sort(CC_info, CC_info + current_CC);
sort(values, values+3);
for(int i=0; i<2; i++){
bool can = false;
for(int j=0; j<current_CC; j++){
if(CC_info[j].first >= values[i].first){
for(int z = CC_info[j].first-1; z >= CC_info[j].first - values[i].first; z--)
res[CC[CC_info[j].second][z]] = values[i].second;
CC_info[j].first -= values[i].first;
can = true;
break;
}
}
if(!can) { res = vi(n, 0); return res; }
}
for(int i=0; i<current_CC; i++){
for(int j=CC_info[i].first-1; j >= 0; j--)
res[CC[CC_info[i].second][j]] = values[2].second;
}
return res;
}
