#include <bits/stdc++.h>
#include "split.h"
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;
const int NS = (int)2e5 + 4;
int n;
struct Dsu{
int n;
vector<int> pr, rk;
Dsu(int N):n(N){
pr.resize(n), rk.resize(n);
for(int i = 0; i < n; ++i) pr[i] = i, rk[i] = 1;
}
inline int get(int x){
return x == pr[x] ? x : pr[x] = get(pr[x]);
}
inline bool unite(int x, int y){
x = get(x), y = get(y);
if(x != y){
if(rk[x] < rk[y]) swap(x, y);
pr[y] = x, rk[x] += rk[y];
return true;
}
return false;
}
};
int ca, cb, cc;
vector<int> way[NS], wayt[NS];
int sz[NS], ans[NS], need;
Dsu gr(NS + 4);
void cdfs(int x, int pr){
for(auto&nxt:wayt[x]){
if(nxt == pr){
continue;
}
cdfs(nxt, x);
sz[x] += sz[nxt];
}
sz[x] += 1;
}
void col(int x, int pr){
for(auto&nxt:wayt[x]){
if(nxt == pr){
continue;
}
gr.unite(x, nxt);
col(nxt, x);
}
}
int cget(int x, int pr){
for(auto&nxt:wayt[x]){
if(nxt == pr){
continue;
}
if(sz[nxt] > n / 2){
return cget(nxt, x);
}
}
return x;
}
void adfs(int x, int tcol){
ans[x] = tcol; --need;
for(auto&nxt:wayt[x]){
if(!ans[nxt] && need){
adfs(nxt, tcol);
}
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> P, vector<int> q) {
ios_base::sync_with_stdio(false);
cin.tie(0);
n = N;
int m = (int)P.size();
ca = 1, cb = 2, cc = 3;
if(a > b) swap(a, b), swap(ca, cb);
if(a > c) swap(a, c), swap(ca, cc);
if(b > c) swap(b, c), swap(cb, cc);
Dsu span(n + 4);
for(int i = 1; i <= m; ++i){
int x, y; x = P[i - 1], y = q[i - 1]; ++x, ++y;
if(span.unite(x, y)){
wayt[x].push_back(y), wayt[y].push_back(x);
}
else way[x].push_back(y), way[y].push_back(x);
}
cdfs(1, -1);
int cent = cget(1, -1);
multiset<pair<int, int>> st;
for(auto&nxt:wayt[cent]){
col(nxt, cent);
st.insert({gr.rk[gr.get(nxt)], gr.get(nxt)});
}
for(int i = 1; i <= n; ++i){
for(auto&nxt:way[i]){
if(i == cent || nxt == cent){
continue;
}
auto p = st.end(); --p;
if(p->first >= a) break;
int pi = gr.get(i), pnxt = gr.get(nxt);
if(pi == pnxt) continue;
wayt[i].push_back(nxt), wayt[nxt].push_back(i);
auto si = st.find(make_pair(gr.rk[pi], pi));
auto snxt = st.find(make_pair(gr.rk[pnxt], pnxt));
gr.unite(pi, pnxt);
st.insert(make_pair(gr.rk[gr.get(pi)], gr.get(pi)));
st.erase(si), st.erase(snxt);
}
}
auto p = st.end(); --p;
if(p->first < a){
return vector<int>(n, 0);
}
ans[cent] = cb;
need = a;
adfs(p->second, ca);
need = b - 1;
for(auto&nxt:wayt[cent]){
if(!ans[nxt] && need){
adfs(nxt, cb);
}
}
for(int i = 1; i <= n; ++i){
if(!ans[i]) ans[i] = cc;
}
vector<int> rv(n);
for(int i = 0; i < n; ++i){
rv[i] = ans[i + 1];
}
return rv;
}
