#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define P push
#define I insert
vector<int> edges[200000];
int n,m,a,b,c;
int parent[200000];
int subsiz[200000];
vector<int> ans;
void dfs(int x){
subsiz[x]=1;
for(int i=0;i<edges[x].size();i++){
int y=edges[x][i];
if(y==parent[x])continue;
parent[y]=x;
dfs(y);
subsiz[x]+=subsiz[y];
}
}
void colouring(int toall,int nd,int ucol, int unum,int dcol,int dnum){
for(int i=0;i<n;i++)ans[i]=toall;
queue<int> q;q.P(nd);
ans[nd]=dcol;dnum--;
while(!q.empty() && dnum>0){
int cur=q.front();q.pop();
for(int i=0;i<edges[cur].size();i++){
int y=edges[cur][i];
if(y==parent[cur])continue;
if(dnum<=0)break;
ans[y]=dcol;dnum--;
q.P(y);
}
}
bool visited[n];memset(visited,false,sizeof(visited));
visited[parent[nd]]=true;ans[parent[nd]]=dcol;dnum--;
queue<int> q1;q1.P(parent[nd]);
while(!q1.empty() && unum>0){
int cur=q1.front();q1.pop();
for(int i=0;i<edges[cur].size();i++){
int y=edges[cur][i];
if(y==nd || visited[y])continue;
if(unum<=0)break;
q1.P(y);
ans[y]=ucol;unum--;
visited[y]=true;
}
}
}
void Subtask_1_3(){
parent[0]=0;
dfs(0);
for(int i=0;i<n;i++){
if(subsiz[i]>=a){
if(n-subsiz[i]>=b){colouring(3,i,2,b,1,a);break;}
if(n-subsiz[i]>=c){colouring(2,i,3,c,1,a);break;}
}
if(subsiz[i]>=b){
if(n-subsiz[i]>=a){colouring(3,i,1,a,2,b);break;}
if(n-subsiz[i]>=c){colouring(1,i,3,c,2,b);break;}
}
if(subsiz[i]>=c){
if(n-subsiz[i]>=b){colouring(1,i,2,b,3,c);break;}
if(n-subsiz[i]>=a){colouring(2,i,1,a,3,c);break;}
}
}
return;
}
void Subtask_2(){
bool visited[n];memset(visited,false,sizeof(visited));
for(int i=0;i<n;i++)ans[i]=3;
visited[0]=true;ans[0]=2;b--;
queue<int> q;q.P(0);
while(!q.empty() && b>0){
int cur=q.front();q.pop();
for(int i=0;i<edges[cur].size();i++){
int y=edges[cur][i];
if(visited[y])continue;
if(b<=0)break;
visited[y]=true;
ans[y]=2;b--;
q.P(y);
}
}
for(int i=0;i<n;i++)if(visited[i]==false){ans[i]=1;break;}
return;
}
vector<int> find_split(int N,int A,int B,int C,vector<int> p,vector<int> q) {
n=N;a=A;b=B;c=C;m=p.size();
for(int i=0;i<n;i++)ans.PB(0);
if(a!=1 && m==n)m--;
for(int i=0;i<m;i++){
edges[p[i]].PB(q[i]);
edges[q[i]].PB(p[i]);
}
if(a==1)Subtask_2();
else Subtask_1_3();
return ans;
}
