#include <bits/stdc++.h>
#include "split.h"
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
struct DisjointSet {
vector<int> par, Sz;
void init(int n) { par.resize(n + 5); Sz.resize(n + 5);
REP(i, n) par[i] = i, Sz[i] = 1;}
int get(int u) { return (par[u] == u ? u : par[u] = get(par[u])); }
bool merge(int u, int v) {
u = get(u); v = get(v);
if(u == v) return false;
if(Sz[u] < Sz[v]) swap(u, v);
par[v] = u; Sz[u] += Sz[v];
return true;
}
};
struct updateDisjointSet {
vector<int> par, Sz, total_val; void init(int n) { par.resize(n + 5); Sz.resize(n + 5); total_val.resize(n + 5);
REP(i, n) par[i] = i, Sz[i] = 1; }
void update(int idx, int W) { total_val[idx] = W; }
int get(int u) { return (u == par[u] ? u : par[u] = get(par[u])); }
void merge(int u, int v) {
u = get(u); v = get(v); if(Sz[u] < Sz[v]) swap(u, v);
par[v] = u; Sz[u] += Sz[v]; total_val[u] += total_val[v];
}
};
bool subtaks1(vector<int> p, vector<int> q, int n) {
vector<int> cnt(n); REP(i, (int)q.size()) { cnt[p[i]]++; cnt[q[i]]++; }
REP(i, n) if(cnt[i] >= 3) return false;
return true;
}
bool cmp(const pair<int, int>& a, const pair<int, int>& b) { return a.first < b.first; }
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<pair<int, int>> cmp_list = {{a, 1}, {b, 2}, {c, 3}}; sort(ALL(cmp_list), cmp);
//FORE(it, cmp_list) cout << (*it).second << endl;
DisjointSet dsu, compress; dsu.init(n); compress.init(n);
vector<int> res(n), h(n), Sz(n); vector<pair<int, int>> edges, edgesspanningtree; REP(i, (int)p.size()) {
edges.push_back({p[i], q[i]}); //cout << edges.back().first << " " << edges.back().second << endl;
}
vector<vector<int>> spanningtree, g; spanningtree.resize(n + 5); g.resize(n + 5); int u = 0, v = 0;
FORE(it, edges) {
u = (*it).first; v = (*it).second; if(dsu.merge(u, v)) {
spanningtree[u].push_back(v); spanningtree[v].push_back(u);
//cout << u << " " << v << endl;
edgesspanningtree.push_back({u, v});
}
g[u].push_back(v); g[v].push_back(u);
}
function<void(int, int)> DFS = [&](int u, int p) {
Sz[u] = 1;
FORE(it, spanningtree[u]) if((*it) != p) {
h[(*it)] = h[u] + 1; DFS((*it), u); Sz[u] += Sz[*it];
}
};
function<int(int, int)> FindCentroid = [&](int u, int p) {
FORE(it, spanningtree[u]) if((*it) != p && Sz[(*it)] > n / 2) {
return FindCentroid(*it, u);
}
return u;
};
DFS(1, -1); int centroid = FindCentroid(1, -1); //cout << centroid << endl;
FORE(it, edges) {
if((*it).first != centroid && (*it).second != centroid) {
compress.merge((*it).first, (*it).second);
}
}
vector<pair<int, int>> points; REP(i, n) if(i == compress.get(i)) {
points.push_back({i, 0}); //cout << i << endl;
}
for(auto &[x, y] : points) y = compress.Sz[compress.get(x)]; int cnt = 0;
//cout << "debug points: " << "\n"; FORE(it, points) cout << (*it).first << " " << (*it).second << endl;
function<void(int, int)> DFS_Fill = [&](int u, int p) {
if(cnt == cmp_list[0].first) return;
res[u] = cmp_list[0].second; /*cout << "dbg: " << u << endl;*/ cnt++; if(cnt == cmp_list[0].first) return;
FORE(it, spanningtree[u]) if((*it) != p) {
if(cnt == cmp_list[0].first) return;
DFS_Fill(*it, u);
if(cnt== cmp_list[0].first) return;
}
};
bool check = false; int idx_comp = -1;
FORE(it, points) {
if((*it).second >= cmp_list[0].first && (*it).first != centroid) {
check = true; idx_comp = (*it).first; break; }
}
if(check) {
//cout << "dbg";
//int next_idx = -1; //FORE(it, spanningtree[centroid]) if(compress.get(*it) == idx_comp) { next_idx = (*it); break; }
//cout << "dbg: " << next_idx << endl;
//cout << idx_comp << endl;
DFS_Fill(idx_comp, centroid); queue<int> q; q.push(centroid); cnt = 0; while(q.size()) {
int u = q.front(); q.pop(); cnt++; res[u] = cmp_list[1].second;
//cout << "debug bfs: " << u << endl;
if(cnt == cmp_list[1].first) break;
FORE(it, spanningtree[u]) if(res[*it] == 0) {
q.push(*it);// cout << "debug bfs: " << (*it) << endl;
}
}
REP(i, n) if(res[i] == 0) res[i] = cmp_list[2].second;
} else {
updateDisjointSet compute; compute.init(n);
// compress is a forest
REP(i, (int)points.size()) compute.update(points[i].first, points[i].second);
vector<vector<int>> newGraph(n + 1); vector<int> Weight(n + 1);
FORE(it, points) Weight[(*it).first] = (*it).second;
int first_comp = -1, second_comp = -1;
FORE(it, edges) {
first_comp = compress.get((*it).first); second_comp = compress.get((*it).second);
if(first_comp != second_comp) {
newGraph[first_comp].push_back(second_comp); newGraph[second_comp].push_back(first_comp);
compute.merge(first_comp, second_comp);
//cout << "debug spanning tree: " << (*it).first << " " << (*it).second << endl;
}
//cout << "debug spanning tree: " << (*it).first << " " << (*it).second << endl;
}
bool check_ans = false; int start_bfs = 0; vector<bool> check(n + 1), allow(n + 1);
REP(i, n) if(compute.total_val[i] >= cmp_list[0].first) { check_ans = true; start_bfs = i; break; }
if(check_ans) {
//cout << "dbg";
queue<int> q; int sumWeight = 0;
q.push(start_bfs); while(q.size()) {
int u = q.front(); check[u] = true; q.pop();
sumWeight += Weight[u]; if(sumWeight >= cmp_list[0].first) break;
else {
FORE(it, newGraph[u]) if(!check[(*it)]) q.push(*it);
}
}
REP(i, n) if(check[compress.get(i)]) allow[i] = true;
while(q.size()) q.pop(); q.push(start_bfs); int cnt = 0; while(q.size()) {
int u = q.front(); res[u] = cmp_list[0].second; cnt++; q.pop(); if(cnt == cmp_list[0].first) break;
else {
FORE(it, g[u]) if(res[*it] == 0) q.push(*it);
}
} while(q.size()) q.pop(); q.push(centroid); cnt = 0; while(q.size()) {
int u = q.front(); q.pop(); cnt++; res[u] = cmp_list[1].second;
if(cnt == cmp_list[1].first) break;
FORE(it, spanningtree[u]) if(res[*it] == 0) {
q.push(*it);
}
}
REP(i, n) if(res[i] == 0) res[i] = cmp_list[2].second;
}
}
//cout << "dbg";
return res;
}
