#include "split.h"
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define maxn 100010
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define ll long long
#define ii pair<int,int>
using namespace std;
int maxdegree, mk[maxn], cnt, subt[maxn], staff, N, cy;
vector<int> g[maxn], res, pres;
ii f;
void dfs_1(int u,int p,int d){
if( mk[u] ) return;
db(u)
pres.push_back(u);
mk[u] = 1;
f = max( f , { d , u } );
for( auto v : g[u] )
if( v != p )
dfs_1(v,u,d+1);
}
void dfs_2(int u,int limit){
if( cnt == limit ) return;
mk[u] = 1;
cnt ++;
if( cnt == limit ) return;
for( auto v : g[u] )
if( !mk[v] )
dfs_2(v,limit);
}
void dfs_4(int u,int p,int color,int cx){
if( cy == cx ) return;
res[u-1] = color;
cy++;
if( cy == cx ) return;
for( auto v : g[u] )
if( v != p )
dfs_4(v,u,color,cx);
}
void dfs_3(int u,int p,int a,int b,int c){
subt[u] = 1;
for( auto v : g[u] ){
if( v == p ) continue;
dfs_3(v,u,a,b,c);
subt[u] += subt[v];
}
if( subt[u] >= a && N - subt[u] >= b && staff == 0 ){
cy = 0;
dfs_4(u,p,1,a);
cy = 0;
dfs_4(p,u,2,b);
staff = 3;
}
if( subt[u] >= b && N - subt[u] >= a && staff == 0 ){
cy = 0;
dfs_4(u,p,2,b);
cy = 0;
dfs_4(p,u,1,a);
staff = 3;
}
if( subt[u] >= a && N - subt[u] >= c && staff == 0 ){
cy = 0;
dfs_4(u,p,1,a);
cy = 0;
dfs_4(p,u,3,c);
staff = 2;
}
if( subt[u] >= c && N - subt[u] >= a && staff == 0 ){
cy = 0;
dfs_4(u,p,3,c);
cy = 0;
dfs_4(p,u,1,a);
staff = 2;
}
if( subt[u] >= b && N - subt[u] >= c && staff == 0 ){
cy = 0;
dfs_4(u,p,2,b);
cy = 0;
dfs_4(p,u,3,c);
staff = 1;
}
if( subt[u] >= c && N - subt[u] >= b && staff == 0 ){
cy = 0;
dfs_4(u,p,3,c);
cy = 0;
dfs_4(p,u,2,b);
staff = 1;
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n;
for(int i=0; i<q.size(); i++){
g[p[i]+1].push_back(q[i]+1);
g[q[i]+1].push_back(p[i]+1);
}
for(int i=1; i<=n; i++){
maxdegree = max( maxdegree , (int)g[i].size() );
res.push_back(0);
}
if( maxdegree <= 2 ){
f = { -1 , -1 };
fill(mk+1,mk+n+1,0);
dfs_1(1,1,0);
pres.clear();
fill(mk+1,mk+n+1,0);
dfs_1(f.s,f.s,0);
for(int i=0; i<pres.size(); i++){
if( i < a ){ res[pres[i]-1] = 1; continue; }
if( i < a + b ){ res[pres[i]-1] = 2; continue; }
res[pres[i]-1] = 3;
}
return res;
}
if( a == 1 ){
fill(mk+1,mk+n+1,0);
cnt = 0;
dfs_2(1,b);
bool put = 1;
for(int i=1; i<=n; i++){
if( mk[i] ){ res[i-1] = 2; continue; }
if( put ){ res[i-1] = 1; put = 0; continue; }
res[i-1] = 3;
}
return res;
}
if( q.size() == n - 1 ){
dfs_3(1,1,a,b,c);
if( staff == 1 )
for(int i=0; i<res.size(); i++)
if( res[i] == 0 ) res[i] = 1;
if( staff == 2 )
for(int i=0; i<res.size(); i++)
if( res[i] == 0 ) res[i] = 2;
if( staff == 3 )
for(int i=0; i<res.size(); i++)
if( res[i] == 0 ) res[i] = 3;
return res;
}
return res;
}
