#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MAXN = 100005;
int N, M, sz[MAXN], parent[MAXN], total[MAXN], centroid, component[MAXN];
vi MST[MAXN], Graph[MAXN], ans;
vector<pii> part ( 3, {0, 0} );
int look ( int node )
{
if ( parent[node] == node )
return node;
return parent[node] = look ( parent[node] );
}
void join ( int nodeA, int nodeB )
{
parent[look(nodeB)] = look(nodeA);
}
void pre ( int node, int p = -1 )
{
sz[node] = 1;
for ( auto i : MST[node] )
if ( i != p )
pre ( i, node ), sz[node] += sz[i];
}
int find_centroid ( int node, int p = -1 )
{
for ( auto i : MST[node] )
if ( i != p && 2*sz[i] > sz[0] )
return find_centroid ( i, node );
return node;
}
void paint ( int node, int p, int color )
{
if ( ans[node] )
return;
if ( part[color].first )
{
part[color].first--;
ans[node] = part[color].second;
}
else
ans[node] = part[2].second;
for ( auto i : MST[node] )
if ( i != p )
paint ( i, node, color );
}
void compress ( int root, int node, int p )
{
component[node] = root;
for ( auto i : MST[node] )
if ( i != p )
compress ( root, i, node );
}
void dfs ( int node, int p = -1 )
{
if ( part[0].first > 0 )
paint ( node, centroid, 0 );
for ( auto i : Graph[node] )
if ( i != p )
dfs ( i, node );
}
vi find_split ( int _n, int a, int b, int c, vi p, vi q )
{
part[0] = {a, 1};
part[1] = {b, 2};
part[2] = {c, 3};
sort ( part.begin(), part.end() );
N = _n;
M = p.size();
ans.resize ( N );
for ( int i = 0; i < N; i++ )
parent[i] = i;
for ( int i = 0; i < M; i++ )
{
if ( look ( p[i] ) != look ( q[i] ) )
{
MST[p[i]].push_back ( q[i] );
MST[q[i]].push_back ( p[i] );
join ( p[i], q[i] );
}
}
pre ( 0 );
centroid = find_centroid ( 0 );
pre ( centroid );
component[centroid] = centroid;
for ( auto i : MST[centroid] )
{
if ( sz[i] >= part[0].first )
{
paint ( i, centroid, 0 );
paint ( centroid, -1, 1 );
return ans;
}
compress ( i, i, centroid );
}
for ( int i = 0; i < N; i++ )
parent[i] = i;
for ( int i = 0; i < M; i++ )
{
if ( p[i] == centroid or q[i] == centroid )
continue;
if ( look ( component[p[i]] ) != look ( component[q[i]] ) )
{
join ( component[p[i]], component[q[i]] );
Graph[component[p[i]]].push_back ( component[q[i]] );
Graph[component[q[i]]].push_back ( component[p[i]] );
}
}
for ( auto i : MST[centroid] )
total[look(i)] += sz[i];
for ( int i = 0; i < N; i++ )
{
if ( i == centroid )
continue;
if ( total[look(component[i])] >= part[0].first )
{
dfs ( component[i] );
paint ( centroid, -1, 1 );
return ans;
}
}
for ( auto &i : ans )
i = 0;
return ans;
}
