#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
vt<int> find_split(int N, int X, int Y, int Z, vt<int> P, vt<int> Q) {
ari2 A = {X, 1}, B = {Y, 2}, C = {Z, 3};
if (B > C)
swap(B, C);
if (A > B)
swap(A, B);
if (B > C)
swap(B, C);
vt<int> adj[N];
bool sub1 = true;
FOR(i, 0, size(P)-1) {
adj[P[i]].push_back(Q[i]);
adj[Q[i]].push_back(P[i]);
sub1 &= size(adj[P[i]]) < 3 && size(adj[Q[i]]) < 3;
}
if (sub1) {
int s = 0;
FOR(i, 0, N-1)
if (size(adj[i]) == 1)
s = i;
int cur = s, p = s;
vt<int> ans(N, C[1]);
while (A[0]--) {
ans[cur] = A[1];
for (int i : adj[cur])
if (i != p) {
p = cur;
cur = i;
break;
}
}
while (B[0]--) {
ans[cur] = B[1];
for (int i : adj[cur])
if (i != p) {
p = cur;
cur = i;
break;
}
}
return ans;
}
if (size(P) == N-1) {
#ifdef DEBUG
cout << "LOL\n";
#endif
int szs[N];
function<int(int, int)> calc_sizes = [&](int i, int p) {
#ifdef DEBUG
cout << "cs: " << i << '\n';
#endif
szs[i] = 1;
for (int j : adj[i])
if (j != p)
szs[i] += calc_sizes(j, i);
return szs[i];
};
calc_sizes(0, 0);
function<void(int, int, ari2&, vt<int>&)> dfs = [&](int i, int p, ari2 &v, vt<int> &ans) {
#ifdef DEBUG
cout << "dfs: " << i << '\n';
#endif
if (!v[0])
return;
ans[i] = v[1];
v[0]--;
for (int j : adj[i])
if (j != p)
dfs(j, i, v, ans);
};
vt<int> ans(N, C[1]);
bool found = false;
function<void(int, int)> reroot = [&](int i, int p) {
if (found)
return;
#ifdef DEBUG
cout << "reroot " << i << '\n';
#endif
for (int j : adj[i])
if (szs[i] - szs[j] >= A[0] && szs[j] >= B[0]) {
dfs(i, j, A, ans);
dfs(j, i, B, ans);
found = true;
return;
}
for (int j : adj[i])
if (j != p) {
int x = szs[j];
szs[j] = N;
szs[i] -= x;
reroot(j, i);
szs[i] += x;
szs[j] = x;
}
};
reroot(0, 0);
if (found)
return ans;
return vt<int>(N, 0);
}
if (A[0] == 1) {
bool seen[N] = {};
int cnt = A[0] + B[0];
function<void(int)> dfs = [&](int i) {
if (seen[i] || !cnt)
return;
seen[i] = true;
cnt--;
for (int j : adj[i])
dfs(j);
};
dfs(0);
vt<int> adj2[N];
FOR(i, 0, N-1)
if (seen[i]) {
#ifdef DEBUG
cout << i << ' ';
#endif
for (int j : adj[i])
if (seen[j])
adj2[i].push_back(j);
}
#ifdef DEBUG
cout << '\n';
#endif
int tin[N], low[N], timer = 0;
memset(tin, -1, sizeof(tin));
bool bad[N] = {};
function<void(int, int)> dfs2 = [&](int i, int p) {
low[i] = tin[i] = timer++;
for (int j : adj2[i]) {
if (j == p || !seen[j])
continue;
if (~tin[j])
low[i] = min(low[i], tin[j]);
else {
dfs2(j, i);
low[i] = min(low[i], low[j]);
if (tin[i] <= low[j] && ~p) {
bad[i] = true;
}
}
}
if (p < 0 && size(adj2[i]) > 1)
bad[i] = true;
};
FOR(r, 0, N-1)
if (seen[r]) {
dfs2(r, -1);
vt<int> ans(N, C[1]);
int special;
FOR(i, 0, N-1)
if (seen[i]) {
ans[i] = B[1];
if (!bad[i])
special = i;
}
#ifdef DEBUG
cout << "special node " << special << '\n';
#endif
ans[special] = A[1];
return ans;
}
}
}
