#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define isz(a) ((signed)a.size())
const int N = 1e5 + 5, M = 2e5 + 5;
int n, m;
vector <pair <int, int>> vcolor;
vector <int> adj[N];
vector <int> ans;
namespace subtask12{
bool check(){
for (auto &[cnt, col]: vcolor){
if (col == 1 and cnt == 1){
return true;
}
}
for (int u = 0; u < n; u++){
if (isz(adj[u]) > 2){
return false;
}
}
return true;
}
vector <bool> chosen;
void dfs(int u){
chosen[u] = true;
ans[u] = vcolor.back().second;
vcolor.back().first--;
if (vcolor.back().first == 0){
vcolor.pop_back();
}
for (auto v: adj[u]){
if (chosen[v]){
continue;
}
dfs(v);
}
}
vector <int> solve(){
chosen.assign(n, false);
int s = 0;
for (int u = 1; u < n; u++){
if (isz(adj[u]) == 1){
s = u;
break;
}
}
dfs(s);
return ans;
}
}
namespace subtask3{
bool check(){
return m == n - 1;
}
int sz[N];
void dfs_sz(int u, int p = -1){
sz[u] = 1;
for (auto v: adj[u]){
if (v == p){
continue;
}
dfs_sz(v, u);
sz[u] += sz[v];
}
}
bool dfs_color(int u, int p, int cnt, int col){
ans[u] = col;
cnt--;
if (cnt == 0){
return true;
}
for (auto v: adj[u]){
if (v == p){
continue;
}
if (dfs_color(v, u, cnt, col)){
return true;
}
}
return false;
}
vector <int> solve(){
dfs_sz(0);
assert(sz[0] == n);
for (int u = 0; u < n; u++){
for (auto v: adj[u]){
if (sz[u] > sz[v]){
continue;
}
if (sz[u] >= vcolor[0].first and n - sz[u] >= vcolor[1].first){
fill(ans.begin(), ans.end(), vcolor[2].second);
dfs_color(u, v, vcolor[0].first, vcolor[0].second);
dfs_color(v, u, vcolor[1].first, vcolor[1].second);
return ans;
}
if (sz[u] >= vcolor[1].first and n - sz[u] >= vcolor[0].first){
fill(ans.begin(), ans.end(), vcolor[2].second);
dfs_color(u, v, vcolor[1].first, vcolor[1].second);
dfs_color(v, u, vcolor[0].first, vcolor[0].second);
return ans;
}
}
}
return ans;
}
}
vector <int> find_split(int _n, int a, int b, int c, vector <int> _u, vector <int> _v){
n = _n; m = isz(_u);
vcolor = {{a, 1}, {b, 2}, {c, 3}};
sort(vcolor.begin(), vcolor.end());
for (int i = 0; i < m; i++){
int u = _u[i], v = _v[i];
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
ans.assign(n, 0);
if (subtask12::check()){
return subtask12::solve();
}
if (subtask3::check()){
return subtask3::solve();
}
return ans;
}
