#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<vector<int>> adj;
vector<bool> vis;
vector<ll> sz;
int smn, mn;
int n;
int a, b, c;
vector<int> res;
int cnt;
void dfs1(int u, int val) {
int col = (val == a ? 1 : (val==b ? 2 : 3));
res[u] = col;
cnt++;
vis[u] = true;
if (cnt==val) return;
for (auto v : adj[u]) {
if (vis[v]) continue;
dfs1(v, val);
}
}
int dfs(int u, int p=-1) {
sz[u] = 1;
vis[u] = true;
for (auto v : adj[u]) {
if (vis[v] || v==p) continue;
sz[u] += dfs(v, u);
}
if (sz[u] >= mn && n-sz[u] >= smn) {
vis.assign(n, false);
vis[u] = true;
cnt=0;
dfs1(p, smn);
cnt=0;
dfs1(u, mn);
return -1e9;
}
if (sz[u] >= smn && n-sz[u] >= mn) {
vis.assign(n, false);
vis[u] = true;
cnt=0;
dfs1(p, mn);
cnt=0;
dfs1(u, smn);
return -1e9;
}
return sz[u];
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
a = A, b = B, c = C;
n = N;
adj.assign(n, {});
int m = p.size();
mn = min({a, b, c});
smn = a+b+c - max({a, b, c}) - mn;
for (int i=0; i<m; i++) {
int u = p[i];
int v = q[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
res.assign(n, 0);
vis.assign(n, false);
sz.assign(n, 0);
dfs(0);
if (sz[0] == n) {
res.assign(n, 0);
return res;
}
else {
for (int i=0; i<n; i++) {
int mx= max({a, b, c});
int val = (mx == a ? 1 : (mx == b ? 2 : 3));
if (res[i] == 0) res[i] = val;
}
return res;
}
}
