#include "split.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<int> resp, sub, pai;
void dfs( int cur, int ancestor ){
pai[cur] = ancestor;
sub[cur] = 1;
for( int viz : adj[cur] ) if( viz != ancestor ){
dfs( viz, cur );
sub[cur] += sub[viz];
}
}
void dfs( int cur, int last, int &resto, int flag ){
if( resto == 0 ) return;
resp[cur] = flag; resto--;
for( int viz : adj[cur] ) if( viz != last ) dfs( viz, cur, resto, flag );
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
adj.resize(n);
resp.resize(n);
sub.resize(n);
pai.resize(n);
for( int i = 0; i < n - 1; i++ ){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
vector<pair<int, int>> comps = { make_pair( a, 1 ), make_pair( b, 2 ), make_pair( c, 3 ) };
sort( comps.begin(), comps.end() );
dfs( 0, 0 );
bool ok = false;
for( int i = 1; i < n; i++ ){
if( sub[i] >= comps[0].first && n - sub[i] >= comps[1].first ){
dfs( i, pai[i], comps[0].first, comps[0].second );
dfs( pai[i], i, comps[1].first, comps[1].second );
ok = true;
break;
}
else if( sub[i] >= comps[1].first && n - sub[i] >= comps[0].first ){
dfs( pai[i], i, comps[0].first, comps[0].second );
dfs( i, pai[i], comps[1].first, comps[1].second );
ok = true;
break;
}
}
if( !ok ) return resp;
for( int &x : resp ) if( x == 0 ) x = comps[2].second;
return resp;
}
