#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 counter=0;
vector<bool> ban;
vector<int> low, disc, sz, ans, par;
vector<pii> vect;
vector<vector<int> > graph;
void dfs(int node, int p){
par[node]=p;
disc[node]=low[node]=counter++;
for (auto num:graph[node])if (num!=p){
if (disc[num]==-1)dfs(num, node), low[node]=min(low[node], low[num]);
else low[node]=min(low[node], disc[num]);
sz[node]+=sz[num];
}
}
void label(int node, int p, int t){
if (!vect[t].fi||ans[node])return;
--vect[t].fi;
ans[node]=vect[t].se;
for (auto num:graph[node])if (num!=p&&!ban[num])label(num, node, t);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
vect.pb(mp(a, 1));
vect.pb(mp(b, 2));
vect.pb(mp(c, 3));
sort(vect.begin(), vect.end());
ans.resize(n, 0);
sz.resize(n, 1);
low.resize(n);
disc.resize(n, -1);
graph.resize(n);
par.resize(n, -1);
ban.resize(n, 0);
for (int i=0; i<p.size(); ++i){
graph[p[i]].pb(q[i]);
graph[q[i]].pb(p[i]);
}
dfs(0, -1);
int mid=-1;
for (int i=0; i<n; ++i){
int mx=0;
for (auto num:graph[i])if (num!=par[i])mx=max(mx, sz[num]);
if (mx<a)mid=i;
}
int cc=sz[mid];
for (auto num:graph[mid])if (num!=par[mid]&&low[num]<disc[mid]&&cc-sz[num]>=vect[0].fi)cc-=sz[num], ban[num]=1;
if (n-cc>=vect[1].fi)swap(vect[0], vect[1]);
if (n-cc>=vect[0].fi){
label(mid, par[mid], 1);
ban.assign(n, 0);
label(par[mid], mid, 0);
for (int i=0; i<n; ++i)if (!ans[i])ans[i]=vect[2].se;
return ans;
}
vector<int> temp(n, 0);
return temp;
}
