#include<bits/stdc++.h>
#include "split.h"
using namespace std;
int one , two , three , ek , dui , tin , siz[100001] , m , vis[100001] , par[100001] , uttor , ans;
int depth[100001] , upore[100001] , heredepth , here , chek , baki , avoid[100001] , unoo , doss , tress;
int typp , bakk;
vector<int> adj[100001] , chs ;
set<int> uno , dos , tres , chose; // tres biggest
void dfs( int me ) {
siz[me] = 1;
vis[me] = 1;
for( int z = 0; z < (int)adj[me].size(); z++ ) {
if( vis[adj[me][z]] == 0 ) {
par[adj[me][z]] = me;
depth[adj[me][z]] = depth[me] + 1;
dfs( adj[me][z] );
upore[me] = min( upore[me] , upore[adj[me][z]] );
siz[me] += siz[adj[me][z]];
}
else upore[me] = min( upore[me] , depth[adj[me][z]] );
}
if( siz[me] >= ek && siz[me] <= dui ) uttor = me;
else if( siz[me] > dui ) {
if( depth[me] > heredepth ) {
heredepth = depth[me];
here = me;
}
}
}
void makeans( int me , int typ ) {
avoid[me] = 1;
if( baki > 0 ) {
if( typ == 1 ) {
uno.insert(me);
baki--;
}
else{
dos.insert(me);
baki--;
}
}
for( int z = 0; z < (int)adj[me].size(); z++ ) {
if( (depth[adj[me][z]] - depth[me]) == 1 && avoid[adj[me][z]] != 1 ) {
if( baki > 0 ) {
makeans( adj[me][z] , typ );
}
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
uttor = -1;
chek = 0;
one = min(a , b);
one = min( one , c );
three = max( a , b );
three = max( three , c );
two = n - (one + three);
ek = one;
dui = (two + three);
if( a == one ) {
unoo = 1;
doss = 2;
tress = 3;
if( b == three ) swap( doss , tress );
}
else if( b == one ) {
unoo = 2;
doss = 1;
tress = 3;
if( a == three ) swap( doss , tress );
}
else{
unoo = 3;
doss = 1;
tress = 2;
if( a == three ) swap( doss , tress );
}
m = p.size();
for( int z = 0; z < m; z++ ) {
adj[p[z]].push_back(q[z]);
adj[q[z]].push_back(p[z]);
}
dfs( 0 );
if( uttor == -1 ) {
int bortoman = ( n - siz[here] );
chs.push_back(0);
for( int z = 0; z < (int)adj[here].size(); z++ ) {
if( depth[adj[here][z]] - depth[here] == 1 ) {
if( bortoman < one && upore[adj[here][z]] < depth[here] ) {
chs.push_back(adj[here][z]);
bortoman += siz[adj[here][z]];
}
}
}
if( bortoman < one ) chek = -1;
if( bortoman >= two ) {
typp = 2;
baki = two;
}
else{
typp = 1;
baki = one;
}
for( int z = 0; z <= n; z++ ) avoid[z] = 0;
avoid[here] = 1;
for( int z = 0; z < (int)chs.size(); z++ ) {
if( baki > 0 ) makeans( chs[z] , typp );
}
avoid[here] = 0;
if( typp == 1 ) {
typp = 2;
baki = two;
}
else{
typp = 1;
baki = one;
}
makeans( here , typp );
}
else{
if( siz[uttor] >= two ) {
typp = 2;
baki = two;
}
else{
typp = 1;
baki = one;
}
makeans( uttor , typp );
if( typp == 1 ) {
typp = 2;
baki = two;
}
else{
typp = 1;
baki = one;
}
makeans( 0 , typp );
}
for( int z = 0; z < n; z++ ) {
if( avoid[z] == 0 ) tres.insert(z);
}
vector<int> finalans(n);
if( chek == -1 ) for( int z = 0; z < n; z++ ) finalans[z] = 0;
else{
for( auto it = uno.begin(); it != uno.end(); ++it ) {
finalans[*it] = unoo;
}
for( auto it = dos.begin(); it != dos.end(); ++it ) {
finalans[*it] = doss;
}
for( auto it = tres.begin(); it != tres.end(); ++it ) {
finalans[*it] = tress;
}
}
return finalans;
}
