#include "split.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
vector<int>adj[maxn];
int high[maxn],sz[maxn];
int n,a,b,c,rt,m,f=0,res[maxn],vis[maxn],s,t,bal[maxn],timea;
vector<pair<int,int>>allv;
pair<int,int>stf[maxn];
bool zird(int u,int v){
return stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second;
}
void clear(){
for(int i=0;i<=n;i++){
vis[i]=0;
sz[i]=high[i]=0;
stf[i]=make_pair(0,0);
bal[i]=0;
}
}
void dfs(int u,int par=-1){
timea++;
stf[u].first=timea;
vis[u]=1;
bal[u]=high[u];
sz[u]=1;
for(auto x:adj[u]){
if(x==par||vis[x]==0){
continue;
}
bal[u]=min(bal[u],high[x]);
}
long long suma=0,z=0;
for(auto x:adj[u]){
if(vis[x]==0){
high[x]=high[u]+1;
dfs(x,u);
sz[u]+=sz[x];
bal[u]=min(bal[u],bal[x]);
if(bal[x]>=high[u]){
f=1;
z=1;
if(sz[x]>=a&&n-sz[x]>=b){
s=x;
t=u;
}
if(sz[x]>=b&&(n-sz[x])>=a){
s=u;
t=x;
}
}else{
suma++;
}
}
}
if(z==1&&s==-1){
if(suma>=a&&n-suma>=b){
rt=u;
}
if(suma>=b&&(n-suma)>=a){
rt=u;
}
}
stf[u].second=timea;
}
void dfssolve(int u,int nar,int w,int ww=0){
if(a==0){
return ;
}
a--;
res[u]=w;
vis[u]=1;
for(auto x:adj[u]){
if(ww==1&&zird(x,nar)){
continue;
}
if(x==nar||vis[x]){
continue;
}
dfssolve(x,nar,w,ww);
}
}
vector<int>rasbor(){
f=0;
dfs(0);
if(f==0){
return {};
}
clear();
dfs(rt);
//cout<<s<<" "<<t<<endl;
if(f==1&&s==-1&&rt==-1){
vector<int>ret;
ret.resize(n);
return ret;
}
clear();
//cout<<s<<" "<<t<<" "<<high[s]<<" "<<high[t]<<endl;
dfssolve(s,t,1,(high[s]<high[t]));
clear();
swap(a,b);
dfssolve(t,s,2,(high[t]<high[s]));
vector<int>ret;
for(int i=0;i<n;i++){
if(res[i]>=1){
ret.push_back(res[i]);
}else{
ret.push_back(3);
}
}
return ret;
}
vector<int>doham(){
vector<int>ret;
int cnt=0;
priority_queue<pair<int,int>>pq;
pq.push(make_pair(high[0],0));
for(int i=0;i<a;i++){
auto x=pq.top();
pq.pop();
if(res[x.second]==1){
i--;
continue;
}
res[x.second]=1;
for(auto y:adj[x.second]){
pq.push(make_pair(high[y],y));
}
}
for(int i=0;i<n;i++){
if(res[i]==1){
continue;
}
if(cnt<b){
res[i]=2;
cnt++;
}else{
res[i]=3;
}
}
for(int i=0;i<n;i++){
if(res[i]>=1){
ret.push_back(res[i]);
}else{
ret.push_back(3);
}
}
return ret;
}
vector<int>solve(){
vector<int>ret=rasbor();
if(ret.size()==0){
ret=doham();
}
for(int i=0;i<n;i++){
if(ret[i]!=0)
ret[i]=allv[ret[i]-1].second;
}
return ret;
}
vector<int> find_split(int n_, int a_, int b_, int c_, vector<int> p, vector<int> q) {
n=n_;
rt=-1;
s=t=-1;
allv.push_back(make_pair(a_,1));
allv.push_back(make_pair(b_,2));
allv.push_back(make_pair(c_,3));
sort(allv.begin(),allv.end());
a=allv[0].first;
b=allv[1].first;
c=allv[2].first;
m=(int)p.size();
for(int i=0;i<m;i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
//solve();
return solve();
}
