#include "split.h"
#include<bits/stdc++.h>
using namespace std;
int cnt;
vector<int> st, num, low;
vector<vector<int>> g, tc;
vector<int> res;
vector<bool> fts;
void dfs(int cur){
num[cur] = cnt;
cnt++;
low[cur] = num[cur];
st[cur] = 1;
for (int next : g[cur]){
if (num[next] != -1){
low[cur] = min(low[cur], num[next]);
continue;
}
dfs(next);
low[cur] = min(low[cur], low[next]);
st[cur] += st[next];
tc[cur].push_back(next);
}
}
int fill(int cur, int x, int c, bool b){
if (res[cur] == c) return 0;
if (x <= 0) return 0;
if (fts[cur] != b) return 0;
res[cur] = c;
int done = 1;
for (int next : g[cur]) done += fill(next, x-done, c, b);
return done;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
int m = p.size();
g.resize(n);
for (int i=0; i<m; i++){
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
tc.resize(n);
st.resize(n);
num.resize(n, -1);
low.resize(n);
cnt = 0;
dfs(0);
vector<int> cc = {a, b, c}, ccc = {1, 2, 3};
if (cc[0] > cc[1]){
swap(cc[0], cc[1]);
swap(ccc[0], ccc[1]);
}
if (cc[1] > cc[2]){
swap(cc[1], cc[2]);
swap(ccc[1], ccc[2]);
}
if (cc[0] > cc[1]){
swap(cc[0], cc[1]);
swap(ccc[0], ccc[1]);
}
int v;
for (int i=0; i<n; i++){
if (st[i] < cc[0]) continue;
bool valid = true;
for (int next : tc[i]){
if (st[next] >= cc[0]) valid = false;
}
if (!valid) continue;
v = i;
break;
}
int s1 = st[v], s2 = n-st[v];
set<int> rem;
for (int next : tc[v]){
if (low[next] < num[v] && s1-st[next] >= cc[0]){
rem.insert(next);
s1 -= st[next];
s2 += st[next];
}
}
fts.resize(n, false);
stack<int> stk;
stk.push(v);
while (!stk.empty()){
int cur = stk.top();
stk.pop();
if (rem.find(cur) != rem.end()) continue;
fts[cur] = true;
for (int next : tc[cur]) stk.push(next);
}
if (s1 >= cc[0] && s2 >= cc[1]){
res.assign(n, ccc[2]);
fill(v, cc[0], ccc[0], true);
fill(0, cc[1], ccc[1], false);
return res;
}
else if (s1 >= cc[1] && s2 >= cc[0]){
res.assign(n, ccc[2]);
fill(v, cc[1], ccc[1], true);
fill(0, cc[0], ccc[0], false);
return res;
}
else return vector<int>(n, 0);
}
