#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define eb emplace_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL
#include "../../../../../MixedFunc/pretty_debug.h"
#else
#define debug(...) //ignore
#endif
vi num, st;
vector<vector<pii>> ed;
int Time;
template<class F>
int dfs(int at, int par, F& f) {
int me = num[at] = ++Time, e, y, top = me;
trav(pa, ed[at]) if (pa.second != par) {
tie(y, e) = pa;
if (num[y]) {
top = min(top, num[y]);
if (num[y] < me) st.push_back(e);
} else {
int si = sz(st);
int up = dfs(y, e, f);
top = min(top, up);
if (up == me) {
st.push_back(e);
f(vi(st.begin() + si, st.end()));
st.resize(si);
}
else if (up < me) st.push_back(e);
else f({e}); // e is a bridge
}
}
return top;
}
template<class F>
void bicomps(F f) {
num.assign(sz(ed), 0);
rep(i,0,sz(ed)) if (!num[i]) dfs(i, -1, f);
}
const vi BAD{};
vector<int> find_split(int n, int a, int b, int c, vi p, vi q) {
debug(n,a,b,c);
debug(p);
debug(q);
// tries to find a split into 2 connected comps.
auto split = [&](){
// find split with side in [L,R] works.
int k = min({a,b,c});
int L = k, R = n-k;
debug(L,R);
ed.resize(n);
rep(i,0,sz(p)) {
ed[p[i]].emplace_back(q[i], i);
ed[q[i]].emplace_back(p[i], i);
}
vector<vi> cmpEd(n); // e-ids in component
vector<vi> bt(n); // block-tree(?): tree of verts and bcc, with edges between them.
bicomps([&](const vi& edg){
int C = sz(bt);
bt.eb();
cmpEd.eb(edg);
trav(i,edg) bt[C].eb(p[i]), bt[C].eb(q[i]);
sort(all(bt[C]));
bt[C].resize(unique(all(bt[C])) - bt[C].begin());
trav(i,bt[C]) bt[i].eb(C);
});
// precal subtree sizes
vi siz(sz(bt)), par(sz(bt));
function<int(int,int)> dfs = [&](int x, int p) {
par[x] = p;
if(x < n) ++siz[x];
trav(y, bt[x]) if(y != p) siz[x] += dfs(y, x);
return siz[x];
};
dfs(0,-1);
debug(siz);
auto comp = [&](int C) {
auto &cmp = bt[C];
int nc = sz(cmp);
debug(nc, cmp);
// build graph for bcc
unordered_map<int,int> toCmpId;
rep(i,0,nc) toCmpId[cmp[i]] = i;
vector<vi> G(nc);
trav(e, cmpEd[C]) {
int a = toCmpId[p[e]], b = toCmpId[q[e]];
G[a].eb(b);
G[b].eb(a);
}
// calculated sizes of subtrees routed at each node
vi ssz(nc,0);
int rt = -1;
rep(i,0,nc) {
int x = cmp[i];
if(par[x] == C) ssz[i] = siz[x];
else rt = i;
}
assert(rt != -1);
ssz[rt] = n - accumulate(all(ssz),0);
debug(ssz);
int mx = max_element(all(ssz)) - ssz.begin();
//int mn = (mx ? 0 : 1); // mn != mx.
if(ssz[mx] > R) return BAD;
// start building split
vi sp = {mx};
vi added(nc);
added[mx] = 1;
int S = 0, bfs = 0;
// now we extend S until S is in [L,R]
// Note: not sure bfs actually works for this?
while(S < L) {
assert(bfs < sz(sp));
int x = sp[bfs++];
S += ssz[x];
trav(y, G[x]) if(!added[y]) {
sp.eb(y);
added[y] = 1;
}
}
assert(L <= S && S <= R);
sp.resize(bfs);
// construct answer
vi ans;
function<void(int,int)> dfs2 = [&](int x, int p) {
if(x < n) ans.eb(x);
trav(y, bt[x]) if(y != p) dfs2(y, x);
};
trav(i,sp) dfs2(cmp[i], C);
assert(sz(ans) == S);
return ans;
};
rep(C,n,sz(bt)) {
auto sp = comp(C);
if(sp != BAD) return sp;
}
return BAD;
};
vi sp = split();
if(sp == BAD) return vi(n,0);
debug(sp);
// find other side of split
sort(all(sp));
vi spC;
for(int i = 0, j = 0; i < n; ++i) {
if(j < sz(sp) && sp[j] == i) ++j;
else spC.eb(i);
}
if(sz(sp) > sz(spC)) swap(sp, spC);
// color vertices
vector<pii> Q = {{a,1}, {b,2}, {c,3}};
sort(all(Q));
vi res(n, Q[2].second);
auto color = [&](vi &vert, int sz, int col) {
assert(!vert.empty());
assert(sz <= sz(vert));
function<void(int)> f = [&](int x) {
if(!binary_search(all(vert), x)) return;
if(res[x] == col) return;
if(sz == 0) return;
res[x] = col; --sz;
trav(y, ed[x]) f(y.first);
};
f(vert[0]);
assert(sz == 0);
};
color(sp, Q[0].first, Q[0].second);
color(spC, Q[1].first, Q[1].second);
return res;
}
