#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
const int N = 100005;
int n;
vector<pair<int, int> > sad;
vector<int> res;
int dsu[N];
int find(int v){
return v == dsu[v]? v : dsu[v] = find(dsu[v]);
}
vector<pair<int, int> > supp;
vector<int> adj1[N];
int sz[N];
int cen(int v, int p){
sz[v] = 1;
int w = -1;
for(auto& x : adj1[v]){
if(x == p) continue;
w = max(w, cen(x, v));
sz[v] += sz[x];
}
if(w != -1) return w;
if(n - sz[v] <= n / 2) return v;
return -1;
}
void mina(int v, int p, int c){
if(sad[c].ff == 0) return;
--sad[c].ff;
res[v] = sad[c].ss;
for(auto& x : adj1[v]){
if(x == p) continue;
mina(x, v, c);
}
}
int col[N];
void pnt(int v, int p, int c){
col[v] = c;
++sz[c];
for(auto& x : adj1[v]){
if(x == p)
continue;
pnt(x, v, c);
}
}
vector<int> adj2[N];
bool vis[N];
int ss;
bool dfs(int v, int r){
vis[v] = 1;
ss += sz[v];
dsu[v] = r;
if(ss >= sad[0].ff) return 1;
for(auto& x : adj2[v])
if(dsu[x] != r)
if(dfs(x, r)) return 1;
return 0;
}
void minari(int v, int c){
if(sad[c].ff == 0) return;
res[v] = sad[c].ss;
--sad[c].ff;
for(auto& x : adj1[v])
if(col[x] == col[v] && !res[x])
minari(x, c);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
::n = n;
res.resize(n);
for(int i = 0; i < n; ++i)
dsu[i] = i;
sad.push_back({a, 1});
sad.push_back({b, 2});
sad.push_back({c, 3});
sort(sad.begin(), sad.end());
for(int i = 0; i < p.size(); ++i){
if(find(p[i]) == find(q[i])) supp.push_back({p[i], q[i]});
else {
dsu[find(p[i])] = find(q[i]);
adj1[p[i]].push_back(q[i]);
adj1[q[i]].push_back(p[i]);
}
}
int r = cen(0, -1);
cen(r, -1);
for(int i = 0; i < adj1[r].size(); ++i){
if(sz[adj1[r][i]] >= sad[0].ff){
mina(adj1[r][i], r, 0);
mina(r, adj1[r][i], 1);
for(int j = 0; j < n; ++j)
if(!res[j])
res[j] = sad[2].ss;
return res;
}
}
for(int i = 0; i < n; ++i)
sz[i] = 0;
for(int i = 0; i < adj1[r].size(); ++i)
pnt(adj1[r][i], r, i + 1);
for(auto& x : supp){
if(col[x.ff] == col[x.ss] || x.ff == r || x.ss == r) continue;
adj2[col[x.ff]].push_back(col[x.ss]);
adj2[col[x.ss]].push_back(col[x.ff]);
}
for(int i = 0; i < n; ++i)
dsu[i] = i;
for(int i = 0; i <= n; ++i){
ss = 0;
if(!vis[i] && dfs(i, i)){
for(int j = 0; j < n; ++j){
col[j] = dsu[col[j]];
if(col[j] != i) col[j] = 0;
}
for(auto& x : supp){
adj1[x.ff].push_back(x.ss);
adj1[x.ss].push_back(x.ff);
}
minari(adj1[r][i - 1], 0);
minari(r, 1);
for(int j = 0; j < n; ++j)
if(!res[j])
res[j] = sad[2].ss;
return res;
}
}
return res;
}
