#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, vis2;
vector<ll> sz;
int smn, mn;
int n;
vector<int> res;
int cnt;
vector<pii> cols;
bool did=false;
void dfs1(int u, int i) {
did = true;
//cout << u << " " << i << endl;
int col = cols[i].second;
res[u] = col;
cnt++;
vis2[u] = true;
int val = cols[i].first;
if (cnt==val) return;
for (auto v : adj[u]) {
if (vis2[v]) continue;
dfs1(v, i);
}
}
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 && !did) {
vis2.assign(n, false);
vis2[u] = true;
cnt=0;
dfs1(p, 1);
cnt=0;
dfs1(u, 0);
return -1e9;
}
if (sz[u] >= smn && n-sz[u] >= mn && !did) {
vis2.assign(n, false);
vis2[u] = true;
cnt=0;
dfs1(p, 0);
cnt=0;
dfs1(u, 1);
return -1e9;
}
return sz[u];
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n = N;
cols.clear();
cols.push_back({a, 1});
cols.push_back({b, 2});
cols.push_back({c, 3});
sort(cols.begin(), cols.end());
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 val = cols[2].second;
if (res[i] == 0) res[i] = val;
}
return res;
}
}
