#include "split.h"
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
vector<vector<int>> A;
ll n;
vector<int> ass;
void dfs(ll u, ll &cnt, ll wr, ll des){
ass[u]=wr; cnt++;
if (cnt==des) return;
for (auto v:A[u]){
if (ass[v]) continue;
dfs(v, cnt, wr, des);
if (cnt==des) return;
}
}
bool check(ll r, ll a, ll b, ll c){
ass.assign(n, 0); queue<ll> proc;
proc.push(r); ass[r]=1; ll cnt=1;
while (cnt<a and !proc.empty()){
auto cur = proc.front(); proc.pop();
for (auto v:A[cur]){
if (ass[v]==0){
ass[v]=1; proc.push(v); cnt++;
}
if (cnt==a) break;
}
}
for (ll i=0; i<n; i++){
if (!ass[i]){
cnt=0; dfs(i, cnt, 2, b);
if (cnt==b) return 1;
else return 0;
}
}
return 0;
}
vector<int> find_split(int N, int ca, int cb, int cc, vector<int> p, vector<int> q) {
n=N; A.resize(n);
for (ll i=0; i<(ll)p.size(); i++){
A[p[i]].push_back(q[i]);
A[q[i]].push_back(p[i]);
}
vector<ll> a = {ca, cb, cc};
vector<ll> perm = {0, 1, 2};
bool ffound=0;
do{
bool found=0;
for (ll i=0; i<n; i++){
if (check(i, a[perm[0]], a[perm[1]], a[perm[2]])){
found=1; break;
}
}
if (found) {ffound=1; break;}
}while (next_permutation(perm.begin(), perm.end()));
if (ffound){
for (ll i=0; i<n; i++){
if (ass[i]==1) ass[i]=perm[0]+1;
else if (ass[i]==2) ass[i]=perm[1]+1;
else ass[i]=perm[2]+1;
}
return ass;
}else{
return vector<int>(n, 0);
}
}
