#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adjList;
vector<bool> visited;
vector<int> sz;
vector<int> ans;
vector<pair<int, int>> values;
int threshold1 = 1e9;
int threshold2 = 1e9;
int node = -1;
int insubtree = -1;
void dfs(int v) {
visited[v] = true;
for (int con: adjList[v]) {
if (!visited[con]) {
dfs(con);
sz[v] += sz[con];
}
}
}
void assign(int v, int mode) {
if (mode) {
if (threshold1) ans[v] = values[insubtree].second, threshold1--;
else ans[v] = values[2].second;
} else {
if (threshold2) ans[v] = values[1 - insubtree].second, threshold2--;
else ans[v] = values[2].second;
}
visited[v] = true;
for (int con: adjList[v]) {
if (!visited[con]) {
assign(con, con == node? 1: mode);
}
}
}
vector<int> find_split(int n, int x, int y, int z, vector<int> u, vector<int> v) {
int m = u.size(); // = v.size()
adjList.clear();
adjList.resize(n);
visited.clear();
visited.resize(n, false);
sz.clear();
sz.resize(n, 1);
for (int i = 0; i < m; i++) {
int a = u[i];
int b = v[i];
adjList[a].push_back(b);
adjList[b].push_back(a);
}
dfs(0);
ans.clear();
ans.resize(n, 0);
values.push_back({x, 1});
values.push_back({y, 2});
values.push_back({z, 3});
sort(values.begin(), values.end());
int a = values[0].first;
int b = values[1].first;
int abovea = 1e9;
int mini1 = -1;
for (int i = 0; i < n; i++) if (sz[i] >= a && sz[i] < abovea) abovea = sz[i], mini1 = i;
if (n - abovea >= b) {
threshold1 = a;
threshold2 = b;
node = mini1;
insubtree = 0;
} else {
int aboveb = 1e9;
int mini2 = -1;
for (int i = 0; i < n; i++) if (sz[i] >= b && sz[i] < aboveb) aboveb = sz[i], mini2 = i;
if (n - aboveb >= a) {
threshold1 = b;
threshold2 = a;
node = mini2;
insubtree = 1;
}
}
if (threshold1 == 1e9) return ans;
for (int i = 0; i < n; i++) visited[i] = false;
assign(0, 0);
return ans;
}
