#include "split.h"
#include <bits/stdc++.h>
#ifdef DEBUG
#define debug(...) println(clog, __VA_ARGS__)
#else
#define debug(...)
#endif
#define forall(i, s, e) for(int i=(s); i<(e); i++)
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using aii = array<int, 2>;
using all = array<ll, 2>;
const int inf = 1e8;
int N;
vector<vi> G, T;
vi S;
vi ans;
vi dv;
vi tin, low;
void fill_subtree(int v, int x, vi &out) {
if(out[v] != -1) return;
out[v] = x;
for(int c:T[v])
fill_subtree(c, x, out);
}
bool divide_ty1(int v, int a) {
debug("DV1 {}", v);
fill_subtree(v, 0, dv);
forall(i, 0, N)
if(dv[i] == -1) dv[i] = 1;
return 1;
}
bool divide_ty2(int v, int a) {
debug("DV2 {}", v);
int s = 1;
dv[v] = 0;
for(int c:T[v]) {
if(low[c] >= tin[v]) {
s += S[c];
debug("fill {} (1)", c);
fill_subtree(c, 0, dv);
}
}
if(s > N-a)
return 0;
for(int c:T[v]) {
if(s >= a) break;
if(low[c] >= tin[v]) continue;
debug("fill {} (2)", c);
s += S[c];
fill_subtree(c, 0, dv);
}
//assert(s >= a);
if(s < a) return 0;
forall(i, 0, N)
if(dv[i] == -1) dv[i] = 1;
return 1;
}
vi find_split(int n, int a, int b, int c, vi p, vi q) {
N = n;
vi x = {a,b,c};
vi w = {1,2,3};
sort(w.begin(), w.end(), [&](int a, int b){ return x[a-1]<x[b-1]; });
a = x[w[0]-1], b=x[w[1]-1], c=x[w[2]-1];
int M = p.size();
G.resize(N);
T.resize(N);
S.resize(N);
tin.resize(N);
low.resize(N);
forall(i, 0, M) {
G[p[i]].push_back(q[i]);
G[q[i]].push_back(p[i]);
}
vb V(N);
int t = 0;
int cand = -1;
int ty = -1;
auto dfs1 = [&](auto dfs1, int v, int p) -> bool {
if(V[v]) return 0;
V[v] = 1;
if(p!=-1) T[p].push_back(v);
low[v] = tin[v] = t++;
S[v] = 1;
for(int c:G[v]) {
if(V[c]) { // back edge
low[v] = min(low[v], low[c]);
continue;
}
dfs1(dfs1, c, v);
low[v] = min(low[v], low[c]);
S[v] += S[c];
}
if(cand == -1) {
if(S[v]>=a && S[v]<=N-a) {
cand = v;
ty = 1;
}
else if(S[v] > N-a) {
cand = v;
ty = 2;
}
}
return 1;
};
dfs1(dfs1, 0, -1);
debug("cand {} ty {}", cand, ty);
//assert(cand != -1); // passa
dv.assign(N, -1);
bool ret;
if(ty == 1) {
ret = divide_ty1(cand, a);
} else {
ret = divide_ty2(cand, a);
}
if(!ret) {
ans.assign(N, 0);
return ans;
}
debug("dv {}", dv);
ans.assign(N, -1);
auto fill = [&](auto fill, int v, int x, int dvi, int &k) -> void {
if(ans[v] != -1 || k==0 || dv[v]!=dvi) return;
ans[v] = x;
k--;
for(int c:G[v])
fill(fill, c, x, dvi, k);
};
int va=-1, vb=-1;
int na = 0;
forall(i, 0, N)
na += (dv[i]==0);
if(na > N/2) {
forall(i, 0, N)
dv[i] = !dv[i];
}
forall(i, 0, N) {
if(dv[i] == 0 && va==-1)
va=i;
if(dv[i] == 1 && vb==-1)
vb=i;
}
int k = a;
fill(fill, va, w[0], 0, k);
assert(k==0);
k = b;
fill(fill, vb, w[1], 1, k);
assert(k == 0);
forall(i, 0, N)
if(ans[i] == -1) ans[i] = w[2];
return ans;
}
