#include <bits/stdc++.h>
#include "split.h"
#pragma GCC optimize("Ofast")
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;
const ll NMAX = 100001;
const ll VMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 1000000;
const ll nr_of_bits = 16;
vector <int> sol;
vector <int> v[NMAX], tree[NMAX], nou[NMAX];
int lvl[NMAX];
int sz[NMAX];
void DFS(int node) {
for(auto x : v[node]) {
if(lvl[x])
continue;
tree[node].push_back(x);
tree[x].push_back(node);
lvl[x] = lvl[node] + 1;
DFS(x);
}
}
int total = 0;
void getsz(int node, int p) {
sz[node] = 1;
for(auto x : tree[node]) {
if(x == p)
continue;
getsz(x, node);
sz[node] += sz[x];
}
total = sz[node];
}
int root;
vector <int> sons[NMAX];
int cc;
int cnt[NMAX];
int findCentroid(int node, int p) {
for(auto x : tree[node]) {
if(x == p)
continue;
if(sz[x] > total / 2)
return findCentroid(x, node);
}
return node;
}
int comp[NMAX];
void baga(int node, int p) {
comp[node] = cc;
cnt[cc]++;
for(auto x : tree[node]) {
if(x == p)
continue;
baga(x, node);
}
}
int col[4];
int cate;
void marcheaza(int node, int p, int cul) {
if(cate == 0)
return;
sol[node] = cul;
cate--;
for(auto x : tree[node]) {
if(x == p || sol[x] != 0)
continue;
marcheaza(x, node, cul);
}
}
int viz[NMAX];
vector <int> cine;
void greedy(int node) {
viz[node] = 1;
if(cate <= 0)
return;
cate -= cnt[node];
cine.push_back(node);
for(auto x : nou[node]) {
if(viz[x])
continue;
greedy(x);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
col[0] = 1;
col[1] = 2;
col[2] = 3;
sol.resize(n);
if(a > b) {
swap(a, b);
swap(col[0], col[1]);
}
if(b > c) {
swap(c, b);
swap(col[2], col[1]);
}
if(a > b) {
swap(a, b);
swap(col[0], col[1]);
}
for(int i = 0; i < p.size(); i++) {
int a = p[i];
int b = q[i];
v[a].push_back(b);
v[b].push_back(a);
}
lvl[0] = 1;
DFS(0);
getsz(0, -1);
root = findCentroid(0, -1);
for(auto x : tree[root]) {
cc = x; /// Componenta poarta numele celui mai inalt din ea (reprezentantul e fiu a root-ului)
baga(x, root);
}
getsz(root, -1);
int maxim = -1;
for(auto x : tree[root]) {
if(maxim == -1 || sz[maxim] < sz[x])
maxim = x;
}
if(sz[maxim] >= a) {
cate = a;
marcheaza(maxim, root, col[0]);
cate = b;
marcheaza(root, -1, col[1]);
for(int i = 0; i < n; i++) {
if(sol[i] == 0)
sol[i] = col[2];
}
return sol;
}
int cnv = -1;
for(int i = 0; i < n; i++) {
if(i == root)
continue;
cnv = comp[i];
for(auto x : v[i]) {
if(x == root)
continue;
if(abs(lvl[i] - lvl[x]) == 1)
continue;
nou[comp[i]].push_back(comp[x]);
}
}
cate = a;
viz[root] = 1;
greedy(cnv);
cate = a;
for(auto x : cine) {
marcheaza(maxim, root, col[0]);
}
if(cate > 0){
for(int i = 0; i < n; i++){
sol[i] = 0;
}
return sol;
}
cate = b;
marcheaza(root, -1, col[1]);
if(cate > 0){
for(int i = 0; i < n; i++){
sol[i] = 0;
}
return sol;
}
for(int i = 0; i < n; i++) {
if(sol[i] == 0)
sol[i] = col[2];
}
return sol;
}
///
