#include "split.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
const int MAXN = 2e5 + 7;
const int INF = 1e9 + 7;
int tin[MAXN], tim;
int clr[MAXN];
int h[MAXN], sz[MAXN], mn[MAXN];
int x, y, z;
vi g[MAXN], palette;
bool invalid = false;
void precalc (int v, int p = 0){
tin[v] = ++tim;
clr[v] = palette[1];
h[v] = h[p] + 1;
sz[v] = 1;
mn[v] = h[v];
for (int to : g[v]){
if (!h[to]){
precalc(to, v);
sz[v] += sz[to];
mn[v] = min(mn[v], mn[to]);
}
else
mn[v] = min(mn[v], h[to]);
}
}
void paint_main (int v, int cclr = 0){
if (cclr == 0 && clr[v] == palette[1]){
x--; y++;
}
else if (cclr == 1 && clr[v] == palette[0]){
x++; y--;
}
clr[v] = palette[cclr];
for (int to : g[v])
if (h[to] - h[v] == 1)
paint_main(to, cclr);
}
void paint (int v, int point){
if (y <= 0)
return;
if (mn[v] < point)
paint_main(v, 1);
else {
for (int to : g[v])
if (h[to] - h[v] == 1 && y > 0)
paint(to, point);
}
}
void dfs (int v){
pi mx = {0, 0};
for (int to : g[v])
if (h[to] - h[v] == 1 && mx.fr < sz[to])
mx = {sz[to], to};
if (x < mx.fr)
dfs(mx.sc);
else {
paint_main(v);
for (int to : g[v])
if (h[to] - h[v] == 1 && y > 0)
paint(to, h[v]);
if (y > 0)
invalid = true;
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
if (a >= b && a >= c){
if (b >= c){
palette = {2, 3, 1};
swap(b, c);
}
else
palette = {3, 2, 1};
swap(a, c);
}
else if (b >= a && b >= c){
if (a >= c)
palette = {1, 3, 2};
else {
palette = {3, 1, 2};
swap(a, c);
}
swap(b, c);
}
else {
if (b >= a){
palette = {2, 1, 3};
swap(a, b);
}
else
palette = {1, 2, 3};
}
x = a;
y = b;
z = c;
for (int i = 0; i < p.size(); i++){
g[p[i] + 1].pb(q[i] + 1);
g[q[i] + 1].pb(p[i] + 1);
}
vector < int > res;
precalc(1);
y -= n;
bool stop = false;
for (int i = 2; i <= n; i++){
if (sz[i] >= a && sz[1] - sz[i] >= b){
paint_main(i);
stop = true;
break;
}
if (sz[i] >= b && sz[1] - sz[i] >= a){
paint_main(1);
paint_main(i, 1);
stop = true;
break;
}
}
if (stop == false)
dfs(1);
if (invalid == true)
while (res.size() < n)
res.pb(0);
else {
vector < pi > temp;
for (int i = 1; i <= n; i++)
temp.pb({tin[i], i});
sort(all(temp));
for (int i = n - 1; i >= 0; i--){
if (clr[temp[i].sc] == palette[0] && x < 0){
clr[temp[i].sc] = palette[2];
x++;
}
else if (clr[temp[i].sc] == palette[1] && y < 0){
clr[temp[i].sc] = palette[2];
y++;
}
}
for (int i = 1; i <= n; i++)
res.pb(clr[i]);
}
return res;
}
