#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int pre[MAXN], pos[MAXN], low[MAXN];
int pai[MAXN], sub[MAXN];
int marc[MAXN], vis[MAXN];
vector<pair<int, int>> ord;
vector<int> adj[MAXN];
vector<int> ans, A, B;
int t = 0;
void dfs_1(int v, int &s){
pre[v] = ++t;
low[v] = pre[v];
sub[v] = 1;
bool ok = true;
for(auto u : adj[v]){
if(!pre[u]){
pai[u] = v;
dfs_1(u, s);
ok &= (sub[u] < ord[0].first);
sub[v] += sub[u];
low[v] = min(low[v], low[u]);
} else if(u != pai[v]) low[v] = min(low[v], pre[u]);
}
ok &= (sub[v] >= ord[0].first);
if(ok) s = v;
pos[v] = t;
}
void dfs_2(int v, int x){
if(x == 0){
A.push_back(v);
} else B.push_back(v);
for(auto u : adj[v]){
if(pre[u] > pre[v]){
dfs_2(u, x);
}
}
}
void dfs_3(int v, int x, int &cnt){
vis[v] = 1;
if(cnt < ord[x].first){
ans[v] = ord[x].second;
} else ans[v] = ord[2].second;
cnt ++;
for(auto u : adj[v]){
if(vis[u] || marc[u] != x) continue;
dfs_3(u, x, cnt);
}
}
bool is_sub(int a, int b){
return pre[b] <= pre[a] && pos[a] <= pos[b];
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
int m = (int) p.size();
for(int i=0; i<m; i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
ord = {{a, 1}, {b, 2}, {c, 3}};
sort(ord.begin(), ord.end());
int s = -1;
dfs_1(0, s);
if(sub[s] >= ord[1].first) swap(ord[0], ord[1]);
A = {s};
for(int i=0; i<n; i++) if(!is_sub(i, s)) B.push_back(i);
for(auto u : adj[s]){
if(pai[u] != s) continue;
int x = (low[u] < pre[s] && (int) B.size() < ord[1].first);
dfs_2(u, x);
}
for(int i=0; i<n; i++) ans.push_back(0);
if((int) B.size() < ord[1].first) return ans;
for(auto x : B) marc[x] = 1;
for(auto x : A) assert(marc[x] == 0);
int cnt = 0;
dfs_3(s, 0, cnt);
cnt = 0;
dfs_3(B[0], 1, cnt);
return ans;
}
