#include "split.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<bool>articulation_point(n,false);
int m = (int)p.size();
vector<set<int>>adj(n);
for (int i = 0;i<m;++i){
if (p[i] == q[i])continue;
adj[p[i]].insert(q[i]);
adj[q[i]].insert(p[i]);
}
vector<int>brr;
brr.push_back(a);
brr.push_back(b);
brr.push_back(c);
vector<int>ord(3);
iota(ord.begin(),ord.end(),0);
sort(ord.begin(),ord.end(),[&](int i,int j){
return brr[i] < brr[j];
});
sort(brr.begin(),brr.end());
vector<int>dfs_low(n,0),dfs_initial(n,0),parent(n,-1);
int time = 0;
int rootnodes = 0;
for (int i = 0;i<n;++i){
function<void(int)>dfs = [&](int u){
dfs_initial[u] = ++time;
dfs_low[u] = ++time;
for (auto x:adj[u]){
if (!dfs_initial[x]){
parent[x] = u;
dfs(x);
if (u == 0){
rootnodes++;
}
if (dfs_low[x] >= dfs_initial[u]){
articulation_point[x] = true;
}
dfs_low[u] = min(dfs_low[u],dfs_low[x]);
}
else if (x!=parent[u]){
dfs_low[u] = min(dfs_low[u],dfs_initial[x]);
}
}
};
rootnodes = 0;
if (!dfs_initial[i])dfs(i);
if (rootnodes > 1){
articulation_point[i] = true;
}
}
int counts = 0;
vector<bool>visited(n,false);
vector<vector<int>>answer;
function<void(int)> dfs2 = [&](int u){
visited[u] = true;
counts++;
for (auto x:adj[u]){
if (!visited[x])dfs2(x);
}
};
int index = -1;
for (int i = 0;i<n;++i){
if (articulation_point[i]){
vector<int>pos;
for (int j = 0;j<n;++j)visited[j] = false;
vector<pair<int,int>>temp_edges;
for (auto x:adj[i]){
adj[x].erase(i);
temp_edges.push_back({x,i});
}
for (auto x:adj[i]){
if (!visited[x]){
counts = 0;
dfs2(x);
pos.push_back(counts);
}
}
sort(pos.rbegin(),pos.rend());
if ((int)pos.size() > 1){
if (pos[0] >= brr[1]){
if (pos[1] + 1 >=brr[0]){
index = i;
}
}
else if (pos[0] + 1>=brr[1]){
if (pos[1] >=brr[0]){
index = i;
}
}
}
for (auto x:temp_edges){
adj[x.first].insert(x.second);
}
}
if (index!=-1)break;
}
vector<int>ans(n,0);
if (index == -1)return ans;
for (auto x:adj[index]){
adj[x].erase(index);
}
function<void(int)> dfs3 = [&](int u){
visited[u] = true;
counts++;
answer.back().push_back(u);
for (auto x:adj[u]){
if (!visited[x])dfs3(x);
}
};
vector<int>pos;
for (int j = 0;j<n;++j)visited[j] = false;
for (auto x:adj[index]){
if (!visited[x]){
counts = 0;
answer.emplace_back();
dfs3(x);
pos.push_back(counts);
}
}
vector<int>order((int)pos.size());
iota(order.begin(),order.end(),0);
sort(order.begin(),order.end(),[&](int i,int j){
return pos[i] > pos[j];
});
if (pos[order[0]] >= brr[1]){
if (pos[order[1]] + 1 >=brr[0]){
for (auto x:answer[order[0]]){
if (!brr[1])break;
brr[1]--;
ans[x] = ord[1] + 1;
}
for (auto x:answer[order[1]]){
if (brr[0] <=1)break;
--brr[0];
ans[x] = ord[0] + 1;
}
ans[index] = ord[0] + 1;
}
}
else if (pos[order[0]] + 1>=brr[1]){
if (pos[order[1]] >=brr[0]){
for (auto x:answer[order[0]]){
if (brr[1]<=1)break;
--brr[1];
ans[x] = ord[1] + 1;
}
for (auto x:answer[order[1]]){
if (!brr[0])break;
--brr[0];
ans[x] = ord[0] + 1;
}
ans[index] = ord[1] + 1;
}
}
for (int i = 0;i<n;++i)if(ans[i]==0)ans[i] = ord[2] + 1;
return ans;
}
