#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) { int m = (int)p.size(); vector<vector<int>> g(n); for (int i = 0; i < m; i++) { g[p[i]].push_back(q[i]); g[q[i]].push_back(p[i]); } vector<int> sz(n, 0); vector<int> pr(n, -1); vector<int> low(n, -1), tin(n, -1); int tt = 0; function<void(int, int)> dfs = [&](int v, int pred) { sz[v] = 1; pr[v] = pred; tin[v] = low[v] = tt++; for (int to : g[v]) { if (to == pred) { continue; } if (tin[to] != -1) { low[v] = min(low[v], tin[to]); } else { dfs(to, v); sz[v] += sz[to]; low[v] = min(low[v], low[to]); } } }; dfs(0, -1); vector<pair<int, int>> ve = {{a, 1}, {b, 2}, {c, 3}}; sort(ve.begin(), ve.end()); vector<int> ans(n, 0); auto color = [&](int from, int cnt, int col, vector<bool>& was) -> void { queue<int> que; que.push(from); was[from] = true; que.push(from); ans[from] = col; int paint = 1; while (!que.empty() && paint < cnt) { int v = que.front(); que.pop(); for (int to : g[v]) { if (was[to]) { continue; } que.push(to); was[to] = true; if (paint < cnt) { paint++; ans[to] = col; } if (paint == col) { return; } } } }; int cent = -1; for (int i = 0; i < n; i++) { if ((n - sz[i]) > n / 2) { continue; } bool ok = true; for (int to : g[i]) { if (pr[to] == i && sz[to] > n / 2) { ok = false; break; } } if (ok) { cent = i; break; } } vector<int> cand; int sum = n - sz[cent]; for (int to : g[cent]) { if (pr[to] != cent) { continue; } if (sz[to] >= ve[0].first) { vector<bool> was(n, false); was[cent] = true; color(to, ve[0].first, ve[0].second, was); was[cent] = false; for (int i = 0; i < n; i++) { if (ans[i] != 0) { was[i] = true; } } color(cent, ve[1].first, ve[1].second, was); for (int i = 0; i < n; i++) { if (ans[i] == 0) { ans[i] = ve.back().second; } } return ans; } if (low[to] < tin[cent]) { cand.push_back(to); sum += sz[to]; } } if (sum >= ve[0].first) { vector<bool> is_a(n, false); vector<bool> sel(n, false); int cur = n - sz[cent]; vector<int> has; for (int v : cand) { if (cur < ve[0].first) { cur += sz[v]; has.push_back(v); sel[v] = true; } } vector<bool> was(n, false); was[cent] = true; for (int to : g[cent]) { if (pr[to] == cent && !sel[to]) { was[to] = true; } } int start = (pr[cent] != -1 ? pr[cent] : has[0]); color(start, ve[0].first, ve[0].second, was); vector<bool> was2(n, false); for (int i = 0; i < n; i++) { if (ans[i] != 0) { was2[i] = true; } } color(cent, ve[1].first, ve[1].second, was2); for (int i = 0; i < n; i++) { if (ans[i] == 0) { ans[i] = ve.back().second; } } return ans; } return ans; }