//#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, v1, v2;
pii x, y, z, curr;
bool valid;
ve<ve<int>> T;
ve<int> Ans;
int dfs(int u, int p) {
int s = 1;
for (int v : T[u]) {
if (v != p) {
s += dfs(v, u);
}
}
if (s < n - s) {
if (s >= x.first && n - s >= y.first) {
v1 = u;
v2 = p;
valid = true;
}
}
else {
if (n - s >= x.first && s >= y.first) {
v1 = p;
v2 = u;
valid = true;
}
}
return s;
}
void assign(int u, int p, int b) {
if (curr.first > 0) {
Ans[u] = curr.second;
curr.first--;
}
for (int v : T[u]) {
if (v != p && v != b) {
assign(v, u, b);
}
}
}
ve<int> find_split(int _n, int a, int b, int c, ve<int> p, ve<int> q) {
int m;
n = _n;
m = (int)p.size();
T = ve<ve<int>>(n);
for (int i = 0; i < m; i++) {
T[p[i]].push_back(q[i]);
T[q[i]].push_back(p[i]);
}
bool cycle = true;
for (int i = 0; i < n; i++) {
if (T[i].size() == 1) cycle = false;
}
if (cycle) {
T = ve<ve<int>>(n);
for (int i = 1; i < m; i++) {
T[p[i]].push_back(q[i]);
T[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];
valid = false;
dfs(0, -1);
if (valid) {
Ans = ve<int>(n, z.second);
curr = x;
assign(v1, -1, v2);
curr = y;
assign(v2, -1, v1);
}
else Ans = ve<int>(n, 0);
return Ans;
}
