#include "split.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<vector<int>> adj(n);
vector<int> prof(n), low(n), sub(n);
for( int i = 0; i < n; i++ ){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
function<int(int, int, int)> dfs_init = [&]( int cur, int pai, int nivel ){
prof[cur] = low[cur] = nivel;
sub[cur] = 1;
for( int viz : adj[cur] ) if( viz != pai ){
if( !prof[viz] ) sub[cur] += dfs_init( viz, cur, nivel + 1 );
low[viz] = min( low[cur], (( prof[viz] < prof[cur] ) ? prof[viz] : low[viz] ) );
}
return sub[cur];
};
function<int(int, int)> find_centroid = [&]( int cur, int tam ){
for( int viz : adj[cur] ) if( prof[viz] == prof[cur] + 1 && sub[viz] > tam/2 ) return find_centroid( viz, tam );
return cur;
};
dfs_init( 0, 0, 1 );
int centroid = find_centroid( 0, n );
vector<pair<int, int>> comp = { make_pair( a, 1 ), make_pair( b, 2 ), make_pair( c, 3 ) };
sort( comp.begin(), comp.end() );
vector<int> resp(n, comp[2].second);
function<void(int, int, int&, int, int)> dfs = [&]( int cur, int pai, int &qtd, int flag, int t ){
if( qtd == 0 || resp[cur] != comp[2].second ) return;
resp[cur] = flag; qtd--;
for( int viz : adj[cur] ) if( t || (abs(prof[viz] - prof[cur]) == 1 && viz != pai) ) dfs( viz, cur, qtd, flag, t);
};
for( int viz : adj[centroid] ){
if( prof[viz] == prof[centroid] + 1 && sub[viz] >= comp[0].first ){
dfs( viz, centroid, comp[0].first, comp[0].second, 0 );
dfs( centroid, viz, comp[1].first, comp[1].second, 0 );
return resp;
}
if( prof[centroid] == prof[viz] + 1 && n - sub[centroid] >= comp[0].first ){
dfs( viz, centroid, comp[0].first, comp[0].second, 0 );
dfs( centroid, viz, comp[1].first, comp[1].second, 0 );
return resp;
}
}
int total = n - sub[centroid];
resp[centroid] = comp[1].second;
comp[1].first--;
for( int viz : adj[centroid] ) if( prof[viz] == prof[centroid] + 1 ){
if( total < comp[0].first && low[viz] < prof[centroid] ) total += sub[viz];
else dfs( viz, centroid, comp[1].first, comp[1].second, 0 );
}
if( total < comp[0].first ) return vector<int>(n, 0);
dfs( 0, 0, comp[0].first, comp[0].second, 1 );
return resp;
}
