#include "split.h"
#include<vector>
#define DIM 100005
using namespace std;
static int viz[DIM], t[DIM], ind[5], d[DIM], e[DIM], niv[DIM];
static vector<int> v[DIM], sol;
static void dfs(int nod){
d[nod] = 1;
e[nod] = niv[nod];
viz[nod] = 1;
for(int i = 0; i < v[nod].size(); i++){
int vecin = v[nod][i];
if(viz[vecin] == 0){
niv[vecin] = niv[nod] + 1;
t[vecin] = nod;
dfs(vecin);
d[nod] += d[vecin];
e[nod] = min(e[nod], e[vecin]);
}
else if(vecin != t[nod]){
e[nod] = min(e[nod], niv[vecin]);
}
}
}
static void dfs2(int nod, int ind, int &s, int nr){
if(s < nr){
s++;
sol[nod] = ind;
}
else{
return;
}
for(int i = 0; i < v[nod].size(); i++){
if(sol[ v[nod][i] ] == 0 && t[ v[nod][i] ] == nod){
dfs2(v[nod][i], ind, s, nr);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int i, j, sum, ok, sa, sb, nod;
ind[1] = 1;
ind[2] = 2;
ind[3] = 3;
if(a > b){
swap(a, b);
swap(ind[1], ind[2]);
}
if(a > c){
swap(a, c);
swap(ind[1], ind[3]);
}
if(b > c){
swap(b, c);
swap(ind[2], ind[3]);
}
for(i = 0; i < p.size(); i++){
v[ p[i] ].push_back(q[i]);
v[ q[i] ].push_back(p[i]);
}
dfs(0);
ok = 0;
sol.resize(n);
for(i = 1; i < n && ok == 0; i++){
sum = d[i];
for(j = 0; j < v[i].size(); j++){
if(sum >= a && n - sum >= b){
ok = 1;
break;
}
nod = v[i][j];
if(t[nod] == i && e[nod] < niv[i]){
sum -= d[nod];
}
}
if(ok == 1){
sa = sb = 0;
sol[i] = ind[1];
sol[ t[i] ] = ind[2];
for(j = j - 1; j >= 0; j--){
nod = v[i][j];
if(t[nod] == i && e[nod] < niv[i]){
dfs2(nod, ind[2], sb, b);
}
}
dfs2(i, ind[1], sa, a);
for(j = t[i]; sb < b; j = t[j]){
dfs2(j, ind[2], sb, b);
}
continue;
}
sum = d[i];
for(j = 0; j < v[i].size(); j++){
if(sum >= b && n - sum >= a){
ok = 1;
break;
}
nod = v[i][j];
if(t[nod] == i && e[nod] < niv[i]){
sum -= d[nod];
}
}
if(ok == 1){
sa = sb = 0;
sol[i] = ind[2];
sol[ t[i] ] = ind[1];
for(j = j - 1; j >= 0; j--){
nod = v[i][j];
if(t[nod] == i && e[nod] < niv[i]){
dfs2(nod, ind[1], sa, a);
}
}
dfs2(i, ind[2], sb, b);
for(j = t[i]; sb < b; j = t[j]){
dfs2(j, ind[2], sb, b);
}
}
}
if(ok == 1){
for(i = 0; i < n; i++){
if(sol[i] == 0){
sol[i] = ind[3];
}
}
}
return sol;
}
