#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))
ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> ans(n,0);
vii d(n);
int m=p.size();
REP(i,0,m){
d[p[i]].PB(q[i]);
d[q[i]].PB(p[i]);
}
if(a==1){
queue<int> pq;
pq.push(0);
REP(i,0,b){
int k=pq.front();
pq.pop();
if(ans[k]!=0){
i--;
continue;
}
ans[k]=2;
for(auto u:d[k])if(ans[u]==0)pq.push(u);
}
REP(i,0,n)if(ans[i]!=2){
ans[i]=1;
break;
}
REP(i,0,n)if(ans[i]==0)ans[i]=3;
return ans;
}
queue<int> pq;
int x=0;
vi vis(n,0);
pq.push(0);
while(!pq.empty()){
int k=pq.front();
pq.pop();
if(vis[k]==1)continue;
vis[k]=1;
x=k;
for(auto u:d[k])pq.push(u);
}
vi par(n,-1);
pq.push(x);
int y=x;
vis.clear();
vis.resize(n,0);
while(!pq.empty()){
int k=pq.front();
pq.pop();
if(vis[k]==1)continue;
vis[k]=1;
y=k;
for(auto u:d[k]){
if(vis[u]==1)continue;
par[u]=k;
pq.push(u);
}
}
vi arr;
arr.PB(y);
while(par[y]!=-1){
arr.PB(par[y]);
y=par[y];
}
int g=arr.size();
pii e={{a,1},{b,2},{c,3}};
sort(e.begin(),e.end());
int l=e[0].F,r=e[0].S;
int pos=0;
while(l>0){
pq.push(arr[pos]);
while(l>0&&!pq.empty()){
int k=pq.front();
pq.pop();
if(k==arr[pos+1]||ans[k]!=0)continue;
ans[k]=r;l--;
for(auto u:d[k])pq.push(u);
}
pos++;
}
l=e[1].F;r=e[1].S;
pq=queue<int>();
while(l>0&&pos<g){
pq.push(arr[pos]);
while(l>0&&!pq.empty()){
int k=pq.front();
pq.pop();
if((pos<n&&k==arr[pos+1])||ans[k]!=0)continue;
ans[k]=r;l--;
for(auto u:d[k])pq.push(u);
}
pos++;
}
if(l>0){
REP(i,0,n)ans[i]=0;
return ans;
}
REP(i,0,n)if(ans[i]==0)ans[i]=e[2].S;
return ans;
}
