#include "split.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> e[100010];
vector<int> res;
int n;
void color(int now,int c,int &num){
if(num==0)return;
res[now]=c;
num--;
for(auto x:e[now]){
if(res[x])continue;
color(x,c,num);
}
return;
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n=N;
int cor[3]={a,b,c};
res.resize(n);
for(int i=0;i<p.size();i++){
e[p[i]].push_back(q[i]);
e[q[i]].push_back(p[i]);
}
int cnt=1;
for(int i=0;i<n;i++){
if(e[i].size()==1){
color(i,cnt,cor[cnt-1]);
cnt++;
}
}
if(cnt==1){
color(0,cnt,cor[cnt-1]);
for(int i=0;i<n;i++){
if(res[i]==0){
color(i,2,cor[1]);
break;
}
}
}
for(int i=0;i<n;i++){
if(res[i]==0)res[i]=3;
}
return res;
}
