#include "split.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
vector<int>parent;
vector<int>sz;
void build(int n){
parent.resize(n);
sz.resize(n);
for (int i = 0;i<n;++i){
parent[i] = i;
sz[i] = 1;
}
}
int findsets(int v){
if (v == parent[v])return v;
parent[v] = findsets(parent[v]);
return parent[v];
}
bool unionset(int u,int v){
u = findsets(u);
v = findsets(v);
if (u == v)return false;
if (sz[u] < sz[v])swap(u,v);
parent[v] = u;
sz[u]+=sz[v];
return true;
}
};
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>ans(n,0);
if (m == n - 1){
vector<int>sz(n);
vector<int>parent(n,-1);
function<void(int)>dfs_tree =[&](int u){
sz[u] = 1;
for (auto x:adj[u]){
if (x == parent[u])continue;
parent[x] = u;
dfs_tree(x);
sz[u]+=sz[x];
}
};
dfs_tree(0);
vector<int>order(n);
iota(order.begin(),order.end(),0);
sort(order.begin(),order.end(),[&](int i,int j){
return sz[i] < sz[j];
});
int index = -1;
for (int i = 0;i<n;++i){
if (sz[order[i]] >= brr[0] && n - sz[order[i]] >=brr[1]){
index = i;
break;
}
else if (sz[order[i]]>=brr[1] && n - sz[order[i]]>=brr[0]){
index = i;
break;
}
}
if (index == -1)return ans;
int v = 0;
function<void(int,int)>mark = [&](int u,int c){
if (v<=0)return;
if (ans[u]!=0)return;
ans[u] = c;
--v;
for (auto x:adj[u]){
if (x == parent[u])continue;
mark(x,c);
}
};
if (sz[order[index]] >=brr[0] && n - sz[order[index]] >=brr[1]){
v = brr[0];
mark(order[index],ord[0] + 1);
v = brr[1];
mark(0,ord[1] + 1);
}
else if (sz[order[index]]>=brr[1] && n - sz[order[index]] >=brr[0]){
v = brr[1];
mark(order[index],ord[1] + 1);
v = brr[0];
mark(0,ord[0] + 1);
}
for (int i = 0;i<n;++i){
if (ans[i] == 0)ans[i] = ord[2] + 1;
}
return ans;
}
if (n <=2500 && m <=5000){
bool found = false;
for (int i = 0;i<n;++i){
DSU st;
st.build(n);
for (int j = 0;j<m;++j){
if (p[j] == i || q[j] == i)continue;
st.unionset(p[i],p[j]);
}
vector<bool>visited(n,false);
vector<pair<int,int>>got;
for (int j = 0;j<n;++j){
if (i == j)continue;
int temp =st.findsets(j);
if (!visited[temp]){
visited[temp] = true;
got.push_back({st.sz[temp],temp});
}
}
sort(got.rbegin(),got.rend());
if ((int)got.size() > 1){
if (got[0].first >=brr[1] && got[1].first + 1>=brr[0]){
for (int j = 0;j<n;++j){
if (st.findsets(j) == got[0].second && brr[1]){
brr[1]--;
ans[j] = ord[1] + 1;
}
else if (st.findsets(j) == got[1].second && brr[0]){
brr[0]--;
ans[j] = ord[0] + 1;
}
}
if (brr[0]){
ans[i] = ord[0] + 1;
}
found = true;
}
else if (got[0].first + 1>=brr[1] && got[1].first>=brr[0]){
for (int j = 0;j<n;++j){
if (st.findsets(j) == got[0].second && brr[1]){
brr[1]--;
ans[j] = ord[1] + 1;
}
else if (st.findsets(j) == got[1].second && brr[0]){
brr[0]--;
ans[j] = ord[0] + 1;
}
}
if (brr[1]){
ans[i] = ord[1] + 1;
}
found = true;
}
}
else if ((int)got.size() == 1){
if (got[0].first>=brr[1] && brr[0]<=1){
for (int j = 0;j<n;++j){
if (st.findsets(j) == got[0].second && brr[1]){
brr[1]--;
ans[j] = ord[1] + 1;
}
}
}
if (brr[0]){
ans[i] = ord[0] + 1;
}
found = true;
}
if (found)break;
}
if (!found)return ans;
for (int i = 0;i<n;++i){
if (ans[i] == 0)ans[i] = ord[2] + 1;
}
return ans;
}
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;
}
}
}
else if ((int)pos.size() > 0){
if (pos[0] >=brr[1]){
if (brr[0]<=1){
index = i;
}
}
}
for (auto x:temp_edges){
adj[x.first].insert(x.second);
}
}
if (index!=-1)break;
}
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.size() > 1){
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;
}
}
}
else{
if (pos[order[0]] >=brr[1]){
if (brr[0]<=1){
for (auto x:answer[order[0]]){
if (!brr[1])break;
--brr[1];
ans[x] = ord[1] + 1;
}
if (brr[0] == 1){
ans[index] = ord[0] + 1;
}
}
}
}
for (int i = 0;i<n;++i)if(ans[i]==0)ans[i] = ord[2] + 1;
return ans;
}
