//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;
int n, cnt;
bool found, sol;
pii x, y, z;
tuple<int, int, int> bottom, top;
ve<int> Num, Low, Size;
ve<bool> B;
ve<ve<int>> G, C;
void dfs(int u, int p) {
cnt++;
Num[u] = cnt;
Low[u] = cnt;
Size[u] = 1;
bool valid = true;
for (int v : G[u]) {
if (Num[v] == 0) {
dfs(v, u);
Low[u] = min(Low[u], Low[v]);
Size[u] += Size[v];
if (Size[v] >= x.first) valid = false;
C[u].push_back(v);
}
else if (v != p) Low[u] = min(Low[u], Num[v]);
}
if (Size[u] < x.first) valid = false;
if (valid && !found) {
found = true;
int curr = Size[u];
for (int v : C[u]) {
if (Low[v] < Num[u]) {
if (curr - Size[v] >= x.first) {
curr -= Size[v];
B[v] = true;
}
}
}
int opp = n - curr;
if (opp >= y.first) {
sol = true;
top = {y.first, y.second, p};
bottom = {x.first, x.second, u};
}
else if (opp >= x.first) {
sol = true;
top = {x.first, x.second, p};
bottom = {y.first, y.second, u};
}
}
}
ve<int> find_split(int _n, int a, int b, int c, ve<int> p, ve<int> q) {
int m;
ve<int> Ans;
queue<int> Q;
n = _n;
m = (int)p.size();
Num = ve<int>(n);
Low = ve<int>(n);
Size = ve<int>(n);
B = ve<bool>(n);
G = ve<ve<int>>(n);
C = ve<ve<int>>(n);
for (int i = 0; i < m; i++) {
G[p[i]].push_back(q[i]);
G[q[i]].push_back(p[i]);
}
ve<pii> A = {{a, 1}, {b, 2}, {c, 3}};
sort(A.begin(), A.end());
x = A[0];
y = A[1];
z = A[2];
cnt = 0;
found = false;
sol = false;
dfs(0, -1);
if (sol) {
Ans = ve<int>(n, z.second);
int sz, t, s;
tie(sz, t, s) = bottom;
sz--;
Ans[s] = t;
Q.push(s);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int v : C[u]) {
if (!B[v]) {
if (sz > 0) {
sz--;
Ans[v] = t;
Q.push(v);
}
}
}
}
tie(sz, t, s) = top;
sz--;
Ans[s] = t;
Q.push(s);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int v : G[u]) {
if (Ans[v] == z.second) {
if (sz > 0) {
sz--;
Ans[v] = t;
Q.push(v);
}
}
}
}
}
else Ans = ve<int>(n);
return Ans;
}
