#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
bool sub1 = true, sub2 = true, sub3 = true, sub4 = true;
int n, m, A, B, C, sz[N];
vector < int > ans;
vector < int > gr[N];
vector < pair < int, int > >cl;
vector < int > Subtask1(){
vector < int > ans(n,0);
int fath = -1, start = 0;
for( int i = 0; i < n; i ++ ){
if( gr[i].size() == 1 )start = i;
}
while( A + B + C > 0 ){
if( A > 0 ){
ans[start] = 1;
A--;
}else if( B > 0 ){
ans[start] = 2;
B --;
}else{
ans[start] = 3;
C --;
}
if( gr[start][0] != fath ){
fath = start;
start = gr[start][0];
}else if( gr[start].size() > 1 ){
fath = start;
start = gr[start][1];
}
}return ans;
}
vector < int > Subtask2(){
vector < int > ans(n, 3);
queue < int > q;
q.push(0); ans[0] = 2;B--;
while(!q.empty() && B > 0){
int v = q.front();q.pop();
for( auto to: gr[v] ){
if( B > 0 && ans[to] == 3 ){
q.push(to); ans[to] = 2; B--;
}
}
}for( int i = 0; i < n; i ++ )if( ans[i] == 3 ){ans[i]=1;break;}
return ans;
}
void build( int v, int f ){
sz[v] = 1;
for( auto to: gr[v] ){
if( to != f ){
build(to, v);
sz[v] += sz[to];
}
}
}
void fil( int v, int f, int x ){
if( cl[x].first == 0 ) return;
ans[v] = cl[x].second;
cl[x].first --;
for( auto to: gr[v] ){
if( to != f ) fil(to, v, x);
}
}
bool dfs( int v, int f ){
vector < pair < int, int > >children;
for( auto to: gr[v] ){
children.push_back({sz[to], to});
}
sort(children.begin(),children.end());
for( size_t i = 0; i < children.size(); i ++ ){
if( children[i].first >= cl[0].first && sz[v] - children[i].first >= cl[1].first ){
fil(children[i].second, v, 0);
fil(v, children[i].second, 1);
return true;
}
}
for( size_t i = 0; i < children.size(); i ++ ){
if( children[i].first >= cl[1].first && sz[v] - children[i].first >= cl[0].first ){
fil( children[i].second, v, 1);
fil( v, children[i].second, 0);
return true;
}
}
for( auto to: gr[v] ){
if( to != f ){
sz[v] -= sz[to]; sz[to] += sz[v];
if( dfs(to,v) ) return true;
}
}
return false;
}
vector < int > Subtask3(){
cl.push_back({A,1}); cl.push_back({B,2}); cl.push_back({C,3});
sort(cl.begin(), cl.end());
ans.resize(n); build(0, -1);
if( dfs(0,-1) ){
for( int i = 0; i < n; i ++ )if( !ans[i] ) ans[i] = cl[2].second;
}return ans;
}
vector < int > Subtask4(){
return {};
}
vector<int> find_split(int nn, int aa, int bb, int cc, vector<int> pp, vector<int> qq) {
n = nn; m = pp.size(); A = aa; B = bb; C = cc;
if( m >= n )sub3 = false;
if( n > 2500 || m > 5000 ) sub4 = false;
if( A > 1 ) sub2 = false;
for( int i = 0; i < m; i ++ ){
gr[pp[i]].push_back(qq[i]);
gr[qq[i]].push_back(pp[i]);
}
for( int i = 0; i < n; i ++ ){
if( gr[i].size() > 2 )sub1 = false;
}
if( sub1 ){
return Subtask1();
}
if( sub2 ){
return Subtask2();
}
if( sub3 ){
return Subtask3();
}
if( sub4 ){
return Subtask4();
}
return {};
}
