#include <bits/stdc++.h>
#include "split.h"
using namespace std;
typedef long long ll;
vector<vector<ll>> adj;
vector<bool> vst;
vector<ll> subSize;
vector<ll> parent;
vector<int> res;
ll dfs(ll node) {
vst[node] = true;
ll sum = 1;
for (auto &e : adj[node]) {
if (!vst[e]) {
sum += dfs(e);
}
else {
parent[node] = e;
}
}
subSize[node] = sum;
return sum;
}
int subG, subGVal;
void dfs2(ll node) {
if (subGVal-- > 0) {
res[node] = subG;
}
else {
return;
}
vst[node] = true;
for (auto &e : adj[node]) {
if (e == parent[node]) continue;
dfs2(e);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m = p.size();
res = vector<int>(n);
adj = vector<vector<ll>>(n);
parent = vector<ll>(n);
subSize = vector<ll>(n);
for (int i = 0; i < m; i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
vst = vector<bool>(n);
subSize[0] = dfs(0);
bool possible = 0;
ll id = 0;
ll low = min({a, b, c}), high = n - min({a, b, c});
for (int i = 0; i < n; i++) {
if (subSize[i] >= low && subSize[i] <= high) { possible = 1; id = i; }
}
if (!possible) {
return res;
}
vst = vector<bool>(n);
vector<pair<ll, ll>> g;
g.push_back({a, 1});
g.push_back({b, 2});
g.push_back({c, 3});
sort(g.begin(), g.end());
subG = subSize[id] < n/2 ? g[0].second : g[1].second;
subGVal = subSize[id] < n/2 ? g[0].first : g[1].first;
dfs2(id);
ll pr = parent[id];
subG = subSize[id] >= n/2 ? g[0].second : g[1].second;
subGVal = subSize[id] >= n/2 ? g[0].first : g[1].first;
dfs(id);
dfs2(pr);
for (auto &e : res) {
if (!e) e = g[2].second;
}
return res;
}
