#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int N, M, cnt;
int sub[MAXN];
int low[MAXN];
int dis[MAXN];
pair<int,int> S[3];
vector<int> adj[MAXN];
vector<int> ans;
void dfs2(int now,int x) {
if (ans[now]||!cnt) return;
cnt--;
ans[now]=x;
for (int next : adj[now]) {
if (dis[next]>=dis[now]) dfs2(next,x);
}
}
int dfs(int now) {
if (sub[now]||!ans.empty()) return 0;
sub[now]=1;
dis[now]=low[now]=++cnt;
int maks=0;
for (int next : adj[now]) {
int save=dfs(next);
maks=max(maks,save);
sub[now]+=save;
low[now]=min(low[now],dis[next]);
}
if (sub[now]>=S[0].first&&maks<S[0].first) {
int size=N-sub[now];
for (int next : adj[now]) {
if (size>=S[0].first) break;
if (dis[next]<dis[now]) continue;
if (low[next]>=dis[now]) continue;
size+=sub[next];
dis[next]=0;
}
ans=vector<int>(N);
if (size>=S[0].first) {
if (size<S[1].first) {
swap(S[0],S[1]);
}
cnt=S[0].first;
dfs2(now,S[0].second);
memset(dis,0,sizeof(dis));
cnt=S[1].first;
dfs2(0,S[1].second);
for (int i=0;i<N;i++) if (!ans[i]) ans[i]=S[2].second;
}
}
return sub[now];
}
vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q) {
N=n;
M=p.size();
for (int i=0;i<M;i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
S[0]={a,1};
S[1]={b,2};
S[2]={c,3};
sort(S,S+3);
dfs(0);
return ans;
}
