#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
int n;
bool found=0;
vector<int> ans, cc, ooga;
vector<bool> visited;
vector<pii> vect;
vector<vector<int> > graph;
void label(int node, int p, int t){
if (visited[node])return;
if (cc[t]>=vect[t].fi)return;
++cc[t];
ans[node]=vect[t].se;
for (auto num:graph[node])if (num!=p)label(num, node, t);
}
int dfscount(int node){
if (visited[node])return 0;
visited[node]=1;
ooga.pb(node);
int res=1;
for (auto num:graph[node])if (!visited[num])res+=dfscount(num);
return res;
}
bool bfs(int start){
stack<int> q;
ans.assign(n, 0);
int cc=0;
q.push(start);
visited.assign(n, 0);
vector<bool> done(n, 0);
while (q.size()&&cc<vect[0].fi){
int node=q.top();
q.pop();
if (ans[node])continue;
done[node]=1;
visited[node]=1;
ans[node]=vect[0].se;
++cc;
for (auto num:graph[node])if (!visited[num])q.push(num);
}
if (cc<vect[0].fi)return 0;
bool can=0;
for (int i=0; i<n; ++i){
ooga.clear();
if (!done[i]&&!ans[i]&&dfscount(i)>=vect[1].fi){
for (auto a:ooga)done[a]=1, visited[a]=0;
label(i, -1, 1), can=1;
break;
}
for (auto a:ooga)done[a]=1, visited[a]=0;
}
for (int i=0; i<n; ++i)if (!ans[i])ans[i]=vect[2].se;
return can;
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q){
n=N;
cc.resize(4, 0);
vect.pb(mp(a, 1));
vect.pb(mp(b, 2));
vect.pb(mp(c, 3));
sort(vect.begin(), vect.end());
ans.resize(n, 0);
graph.resize(n);
visited.resize(n, 0);
for (int i=0; i<p.size(); ++i){
graph[p[i]].pb(q[i]);
graph[q[i]].pb(p[i]);
}
for (int i=0; i<n; ++i)if (bfs(i))return ans;
vector<int> temp(n, 0);
return temp;
}
