#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int>adj[N];
int col[N], c[3], val[3], lst = 0;
bool visited[N];
int deg[N], sz[N], root = -1, A, B, NN;
void dfs(int node, int parent){
sz[node] = 1;
for(auto i : adj[node]){
if(i == parent) continue;
dfs(i, node);
sz[node] += sz[i];
}
}
bool can_split(int node, int parent){
vector<int> v;
for(auto i : adj[node]){
v.push_back(sz[i]);
}
if(v.size() > 1){
sort(v.rbegin(), v.rend());
int K = 0;
for(auto i : v){
if(i >= A){
K = i;
}
}
if(K != 0 && NN - K >= B){
root = node;
return 1;
}
}
for(auto i : adj[node]){
if(i == parent) continue;
int P = sz[i];
sz[i] = sz[node];
sz[node] = sz[node] - P;
if(can_split(i, node)){
return 1;
}
sz[node] += P;
sz[i] = P;
}
return 0;
}
void dfs_col(int node, int parent, int comp){
if(c[comp] == val[comp]) return;
c[comp]++;
col[node] = comp + 1;
visited[node] = 1;
for(auto i : adj[node]){
if(i == parent || visited[i]) continue;
dfs_col(i, node, comp);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> res;
NN = n;
for(int i = 0; i < p.size(); i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
deg[p[i]]++;
deg[q[i]]++;
}
vector<pair<int, int>>o;
o.push_back({a, 0});
o.push_back({b, 1});
o.push_back({c, 2});
sort(o.begin(), o.end());
A = o[0].first;
B = o[1].first;
val[0] = a;
val[1] = b;
val[2] = c;
dfs(0, 0);
if(!can_split(0, 0)){
for(int i = 0; i < n; i++){
res.push_back(0);
}
return res;
}
dfs(root, -1);
vector<pair<int, int>> v;
for(auto i : adj[root]){
v.push_back({sz[i], i});
}
sort(v.rbegin(), v.rend());
int pr = -1;
for(auto i : v){
if(i.first >= A){
pr = i.second;
}
}
dfs_col(pr, root, o[0].second);
dfs_col(root, -1, o[1].second);
for(int i = 0; i < n; i++){
if(!col[i]){
col[i] = o[2].second + 1;
}
}
for(int i = 0; i < n; i++){
res.push_back(col[i]);
}
return res;
}
