#include "split.h"
#include <bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define pii pair<int,int>
#define fi first
#define se second
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define pb push_back
#define repa(a,b) for(auto a:b)
using namespace std;
const int lim=2e5+5;
vector<int> adj[lim];
int sz[lim];
void dfs(int u, int p=-1){
sz[u]=1;
repa(v,adj[u]){
if(v==p) continue;
dfs(v,u);
sz[u]+=sz[v];
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> res(n,0);
queue<int> Q;
bool vis[n]{};
int d[3]={a,b,c}, u, z;
rep(i,0,p.size()){
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
if(q.size()==n-1){
dfs(0);
pii ord[3]={{a,1},{b,2},{c,3}};
sort(ord,ord+3);
rep(i,0,n){
if((sz[i]>=ord[1].fi && n-sz[i]>=ord[0].fi)) swap(ord[0],ord[1]);
if(!(sz[i]>=ord[0].fi && n-sz[i]>=ord[1].fi)) continue;
Q.push(i);
Q.push(0);
Q.push(0);
Q.push(1);
while(Q.size()){
u=Q.front();
Q.pop();
z=Q.front();
Q.pop();
if(vis[u]) continue;
vis[u]=true;
if(ord[z].fi){
res[u]=ord[z].se;
ord[z].fi--;
}else res[u]=ord[2].se;
repa(v,adj[u]){
if((!z && sz[v]>sz[u]) || vis[v]) continue;
Q.push(v);
Q.push(z);
}
}
return res;
}
return res;
}
repr(j,3,0){
rep(i,0,n){
if(!vis[i]){
Q.push(i);
while(Q.size()){
u=Q.front();
Q.pop();
if(vis[u]) continue;
vis[u]=true;
res[u]=j+1;
d[j]--;
if(!d[j]) break;
repa(v,adj[u]) if(!vis[v]) Q.push(v);
}
while(Q.size()) Q.pop();
}
if(!d[j]) break;
}
}
return res;
}
