#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
vector<vi> G;
vector<ii> ab;
vector<int> res;
int n,m;
int tam;
bool colorear(int u,int col){
res[u]=col;
tam--;
if(tam==0) return 1;
for(auto &v:G[u]){
if(res[v]==0 && colorear(v,col))
return 1;
}
return 0;
}
bool sepuede(int ro){
for(int i=0;i<n;i++) res[i]=0;
tam=ab[0].first;
colorear(ro,ab[0].second);
int col=4;
bool se=0;
for(int i=0;i<n;i++){
if(res[i]==0){
col++;
tam=ab[1].first;
if(colorear(i,col)){
se=1;
break;
}
}
}
for(int i=0;i<n;i++){
if(res[i]!=ab[0].second && res[i]!=col) res[i]=ab[2].second;;
if(res[i]==col) res[i]=ab[1].second;
}
return se;
}
vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
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());
bool sw=0;
for(int i=0;i<n;i++){
if(sepuede(i)){
sw=1;
break;
}
}
if(!sw) for(int i=0;i<n;i++) res[i]=0;
return res;
}
