#include "split.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 10; int pre[MAXN], pos[MAXN], low[MAXN]; int pai[MAXN], sub[MAXN]; int marc[MAXN], vis[MAXN]; vector<pair<int, int>> ord; vector<int> adj[MAXN]; vector<int> ans, A, B; int t = 0; void dfs_1(int v, int &s){ pre[v] = ++t; low[v] = pre[v]; sub[v] = 1; bool ok = true; for(auto u : adj[v]){ if(!pre[u]){ pai[u] = v; dfs_1(u, s); ok &= (sub[u] < ord[0].first); sub[v] += sub[u]; low[v] = min(low[v], low[u]); } else if(u != pai[v]) low[v] = min(low[v], pre[u]); } ok &= (sub[v] >= ord[0].first); if(ok) s = v; pos[v] = t; } void dfs_2(int v, int x){ if(x == 0){ A.push_back(v); } else B.push_back(v); for(auto u : adj[v]){ if(pre[u] > pre[v]){ dfs_2(u, x); } } } void dfs_3(int v, int x, int &cnt){ vis[v] = 1; if(cnt < ord[x].first){ ans[v] = ord[x].second; } else ans[v] = ord[2].second; cnt ++; for(auto u : adj[v]){ if(vis[u] || marc[u] != x) continue; dfs_3(u, x, cnt); } } bool is_sub(int a, int b){ return pre[b] <= pre[a] && pos[a] <= pos[b]; } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){ int m = (int) p.size(); for(int i=0; i<m; i++){ adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } ord = {{a, 1}, {b, 2}, {c, 3}}; sort(ord.begin(), ord.end()); int s = -1; dfs_1(0, s); if(sub[s] >= ord[1].first) swap(ord[0], ord[1]); A = {s}; for(int i=0; i<n; i++) if(!is_sub(i, s)) B.push_back(i); for(auto u : adj[s]){ if(pai[u] != s) continue; int x = (low[u] < pre[s] && (int) B.size() < ord[1].first); dfs_2(u, x); } for(int i=0; i<n; i++) ans.push_back(0); if((int) B.size() < ord[1].first) return ans; for(auto x : B) marc[x] = 1; for(auto x : A) assert(marc[x] == 0); int cnt = 0; dfs_3(s, 0, cnt); cnt = 0; dfs_3(B[0], 1, cnt); return ans; }