#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
vector<int> adj[MAXN];
vector<int> g[MAXN];
int num[MAXN], low[MAXN], timer = 0;
int sz[MAXN];
int par[MAXN];
int ans[MAXN];
int color[MAXN];
void dfs(int u, int p) {
par[u] = p;
num[u] = low[u] = ++timer;
sz[u] = 1;
for (int v : adj[u]) {
if (v == p) continue;
if (num[v]) {
low[u] = min(low[u], num[v]);
} else {
g[u].emplace_back(v);
g[v].emplace_back(u);
dfs(v, u);
low[u] = min(low[u], low[v]);
sz[u] += sz[v];
}
}
}
void dfsans(int u, int p, int id, int cur, int& cnt, vector<int>* adj) {
if (color[u] != cur) return;
if (cnt == 0) return;
cnt--;
color[u] = id;
for (int v : adj[u]) {
if (v == p) continue;
dfsans(v, u, id, cur, cnt, adj);
if (cnt == 0) return;
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int aa = a, bb = b, cc = c;
map<int, int> mp;
mp[0] = 1;
mp[1] = 2;
mp[2] = 3;
if (a > b) swap(a, b), swap(mp[0], mp[1]);
if (a > c) swap(a, c), swap(mp[0], mp[2]);
if (b > c) swap(b, c), swap(mp[1], mp[2]);
vector<int> res(n, 0);
int m = p.size();
for (int i = 0; i < m; i++) {
adj[p[i]].emplace_back(q[i]);
adj[q[i]].emplace_back(p[i]);
}
dfs(0, -1);
int best_subtree = -1;
int best_size = n + 1;
for (int i = 0; i < n; i++) {
int subtree_size = sz[i];
if (subtree_size >= a) {
if (subtree_size < best_size) {
best_size = subtree_size;
best_subtree = i;
}
}
}
for (int i = 0; i < n; i++) color[i] = 4;
int x = 1e9;
dfsans(best_subtree, par[best_subtree], 3, 4, x, g);
int notsubtree_size = n - best_size;
for (int v : g[best_subtree]) {
if (notsubtree_size >= a) break;
if (v == par[best_subtree]) continue;
if (low[v] >= num[best_subtree]) continue;
notsubtree_size += sz[v];
best_size -= sz[v];
dfsans(v, best_subtree, 4, 3, x, g);
}
if (notsubtree_size < a) return res;
if (notsubtree_size >= b) {
dfsans(0, -1, 1, 4, b, adj);
dfsans(best_subtree, -1, 0, 3, a, adj);
} else {
assert(best_size >= b);
dfsans(0, -1, 0, 4, a, adj);
dfsans(best_subtree, -1, 1, 3, b, adj);
}
for (int i = 0; i < n; i++) {
res[i] = mp[min(color[i], 2)];
}
return res;
}
