#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10, MAXM=2e5+10;
vector<int>v[MAXN], marc(MAXN), pai(MAXN), v2[MAXN];
int m1, m2, aux=-1;
bool ok;
int dfs(int x, int n){
marc[x]=1;
int subsize=1;
for(int k=0;k<v[x].size();k++){
if(marc[v[x][k]]==0){
subsize+=dfs(v[x][k], n);
pai[v[x][k]]=x;
v2[x].push_back(v[x][k]);
v2[v[x][k]].push_back(x);
}
}
if(subsize>=m1 and n-subsize>=m2){
aux=x;
ok=true;
}else if(subsize>=m2 and n-subsize>=m1){
aux=x;
ok=false;
}
return subsize;
}
vector<int>ord1, marc1(MAXN);
void ans1(int x){
marc1[x]=1;
ord1.push_back(x);
for(int k=0;k<v2[x].size();k++){
if(marc1[v2[x][k]]==0 and v2[x][k]!=pai[aux]){
ans1(v2[x][k]);
}
}
}
vector<int>ord2, marc2(MAXN);
void ans2(int x){
marc2[x]=1;
ord2.push_back(x);
for(int k=0;k<v2[x].size();k++){
if(marc2[v2[x][k]]==0 and v2[x][k]!=aux){
ans2(v2[x][k]);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int>n1, vector<int>n2){
int m=n1.size();
vector<int>resp(n, 0);
for(int k=0;k<m;k++){
v[n1[k]].push_back(n2[k]);
v[n2[k]].push_back(n1[k]);
}
m1=min({a, b, c});
int rm1, rm2;
if(m1==a){
rm1=1;
m2=min(b, c);
if(m2==b){
rm2=2;
}else{
rm2=3;
}
}else if(m1==b){
rm1=2;
m2=min(a, c);
if(m2==a){
rm2=1;
}else{
rm2=3;
}
}else{
rm1=3;
m2=min(a, b);
if(m2==a){
rm2=1;
}else{
rm2=2;
}
}
dfs(0, n);
if(aux==-1){
return resp;
}
ans1(aux);
ans2(pai[aux]);
if(ok){
for(int k=0;k<m1;k++){
resp[ord1[k]]=rm1;
}
for(int k=0;k<m2;k++){
resp[ord2[k]]=rm2;
}
}else{
for(int k=0;k<m1;k++){
resp[ord2[k]]=rm1;
}
for(int k=0;k<m2;k++){
resp[ord1[k]]=rm2;
}
}
for(int k=0;k<n;k++){
if(resp[k]==0){
resp[k]=6-rm1-rm2;
}
}
return resp;
}
/*int main()
{
int n, m, a, b, c;
cin>>n>>m>>a>>b>>c;
vector<int>n1(m), n2(m);
for(int k=0;k<m;k++){
cin>>n1[k];
}
for(int k=0;k<m;k++){
cin>>n2[k];
}
vector<int>resp=find_split(n, a, b, c, n1, n2);
for(int k=0;k<n;k++){
cout<<resp[k]<<' ';
}
return 0;
}*/
