#include <bits/stdc++.h>
#include "split.h"
#define sz(x) (int)x.size()
#define mkt make_tuple
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mk make_pair
#define pii pair<int,int>
#define debug printf
#define all(x) x.begin(),x.end()
const int MAXN = 1e5+10 ;
using namespace std ;
int A[3] , N ;
int sub[MAXN] , cor[MAXN] , pai[MAXN] , tam[MAXN] , idx[3] ;
vector<int> adj[MAXN] , tree[MAXN] ;
bool vis[MAXN] ;
vector<pii> outsideSt ;
bool ok = true ;
void findSt(int x, int d = -1 )
{
vis[x] = true ;
sub[x] = 1 ;
for(auto e : adj[x])
{
if(!vis[e])
{
tree[x].pb(e) ;
tree[e].pb(x) ;
findSt(e,x) ;
sub[x] += sub[e] ;
}
else if( e != d ) outsideSt.pb( mk(x,e) ) ;
}
}
void colore(int x, int pai, int c )
{
cor[x] = c ;
for(auto e : tree[x] )
if(pai != e) colore(e, x, c ) ;
}
int find(int x)
{
if(x == pai[x]) return x ;
return pai[x] = find(pai[x]) ;
}
int join(int x, int y)
{
x = find(x) ;
y = find(y) ;
if(x == y) return x ;
if(rand() % 2) swap(x,y) ;
pai[x] = y ;
tam[y] += tam[x] ;
return y;
}
void spin(int x)
{
int mx = -1 ;
for(auto e : tree[x] )
if( mx == -1 || sub[mx] < sub[e] ) mx = e ;
if( sub[mx] >= A[0] && (N-sub[mx]) >= A[0] )
{
if( sub[mx] > N-sub[mx] ) colore(mx, x, 1) ;
else colore(x, mx , 1) ;
}
else if( sub[mx] >= A[0] )
{
sub[x] = N - sub[mx] ;
sub[mx] = N ;
spin(mx) ;
}
else
{
for(int i = 1 ; i <= N ; i++ )
for(auto e : tree[i] )
{
if(i == x || e == x) continue ;
join(i, e) ;
}
for(auto e : outsideSt )
{
if(e.ff == x || e.ss == x) continue ;
int newPai = join(e.ff, e.ss );
if( tam[newPai] < A[0] ) continue ;
if( tam[newPai] > (N-tam[newPai]) )
{
for(int i = 1 ; i <= N ; i++ )
if( find(i) == newPai ) cor[i] = 1 ;
}
else
{
for(int i = 1 ; i <= N ; i++ )
if(find(i) != newPai ) cor[i] = 1 ;
}
return ;
}
ok = false ;
}
}
void pintando(int x, int y)
{
vis[x] = true ;
if( A[y] == 0 ) return ;
A[y]-- ;
for(auto e : adj[x] )
if(!vis[e] && cor[e] == y && A[y] ) pintando(e,y) ;
}
vector<int> find_split(int n , int a1 , int a2 , int a3 , vector<int> p ,vector<int> q )
{
A[0] = a1 ;
A[1] = a2 ;
A[2] = a3 ;
idx[0] = 0 ;
idx[1] = 1 ;
idx[2] = 2 ;
N = n ;
srand(time(0)) ;
sort(idx, idx+3 , [&](int i, int j) { return A[i] < A[j] ; } ) ;
sort(A, A+3) ;
lp(i,1,N+1) pai[i] = i , tam[i] = 1 ;
for(int i = 0 ; i < sz(p) ; i++ )
{
p[i]++ ;
q[i]++ ;
adj[ p[i] ].push_back(q[i]) ;
adj[ q[i] ].pb( p[i] ) ;
}
findSt(1) ;
spin(1) ;
lp(i,1,N+1) vis[i] = false ;
lp(i,1,N+1)
if(cor[i] == 0) { pintando(i,0) ; break ; }
lp(i,1,N+1)
if(cor[i] == 1) { pintando(i,1) ; break ; }
lp(i,1,N+1)
if(!vis[i]) cor[i] = 2 ;
vector<int> vec ;
if(!ok) idx[0] = idx[1] = idx[2] = -1 ;
for(int i = 0 ; i < N ; i++ ) vec.pb( idx[cor[i+1]] + 1 ) ;
return vec ;
}
