#include "split.h" #include <bits/stdc++.h> using namespace std; vector<int> find_split(int n, int A, int B, int C, vector<int> P, vector<int> Q) { array<pair<int, int>, 3> att; att[0] = {A, 1}; att[1] = {B, 2}; att[2] = {C, 3}; sort(att.begin(), att.end()); A = att[0].first; B = att[1].first; C = att[2].first; vector<int> sz(n, 1); vector<vector<int>> adj(n); vector<int> p(n); vector<int> vis(n, 0); vector<int> hgh(n); vector<int> dpth(n, 0); for (size_t i = 0; i < P.size(); i++) { adj[P[i]].push_back(Q[i]); adj[Q[i]].push_back(P[i]); } int base = 0; function<void(int)> dfs = [&](int a) { if (base > 0) return; bool ok = 1; vis[a] = 1; hgh[a] = dpth[a]; for (int x : adj[a]) { if (vis[x]) { if (x != p[a]) hgh[a] = min(hgh[a], dpth[x]); continue; } p[x] = a; dpth[x] = dpth[a]+1; dfs(x); sz[a] += sz[x]; if (sz[x] >= A) { ok = 0; } } if (sz[a] < A) ok = 0; if (ok) { int aus = n-sz[a]; base = a; for (int x : adj[a]) { if (x == 0 || p[x] != a) continue; if (aus >= B) break; if (hgh[x] < dpth[a]) aus += sz[x]; p[x] = p[a]; } if (aus < B) base = -1; } }; p[0] = -1; dfs(0); if (base <= 0) return vector<int> (n, 0); vis = vector<int> (n, -1); int ja = 0, jb = 0; function<void(int)> dfsa = [&](int a) { if (ja < A) { vis[a] = att[0].second; ja++; } else return; for (int x : adj[a]) { if (x == 0 || p[x] != a) continue; dfsa(x); } }; dfsa(base); function<void(int)> dfsb = [&](int a) { vis[a] = 0; if (jb < B) { vis[a] = att[1].second; jb++; } else return; for (int x : adj[a]) { if (vis[x] >= 0) continue; dfsb(x); } }; dfsb(p[base]); for (int i = 0; i < n; i++) { if (vis[i] <= 0) vis[i] = att[2].second; } return vis; }