#include<bits/stdc++.h>
using namespace std;
int m,zx,z,x,d,e,used[100009],ka[10],la[100009];
vector <int> pas,g[100009];
void DFS(int v){
if(ka[zx]==0)
return;
used[v]=1;
pas[v]=zx;
ka[zx]--;
if(ka[zx]==0)
return;
for(vector <int>::iterator it=g[v].begin(); it!=g[v].end(); it++){
if(used[(*it)]==1){
DFS((*it));
if(ka[zx]==0)
return;
}
}
}
void DFS1(int v){
if(ka[zx]==0)
return;
used[v]=1;
pas[v]=zx;
ka[zx]--;
if(ka[zx]==0)
return;
for(vector <int>::iterator it=g[v].begin(); it!=g[v].end(); it++){
if(used[(*it)]==1)
continue;
DFS1((*it));
if(ka[zx]==0)
return;
}
}
vector <int> find_split(int n, int a, int b, int c, vector <int> p, vector <int> q){
pas.resize(n);
ka[1]=a;
ka[2]=b;
ka[3]=c;
zx=0;
m=p.size();
for(int k=0;k<q.size();k++){
g[p[k]].push_back(q[k]);
g[q[k]].push_back(p[k]);
}
if(a!=1){
zx=0;
for(int k=0;k<n;k++){
if(g[k].size()!=1)
continue;
if(used[k]==0){
zx++;
DFS(k);
}
}
if(zx!=0){
for(int k=0;k<n;k++)
if(pas[k]==0)
pas[k]=3;
}
else{
zx=0;
for(int k=0;k<n;k++){
if(used[k]==0){
zx++;
DFS(k);
break;
}
}
for(int k=0;k<n;k++){
if(used[k]==1){
for(vector <int>::iterator it=g[k].begin();it!=g[k].end(); it++){
if(used[(*it)]==1)
continue;
zx++;
DFS((*it));
break;
}
if(zx==2)
break;
}
}
for(int k=0;k<n;k++){
if(used[k]==0){
zx++;
DFS(k);
break;
}
}
}
}else{
zx=2;
DFS1(0);
for(int k=0;k<n;k++){
if(pas[k]==0){
pas[k]=1;
break;
}
}
for(int k=0;k<n;k++)
if(pas[k]==0)
pas[k]=3;
}
return pas;
}
/*main(){
vector <int> v=find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5},
{1, 2, 3, 4, 6, 8, 7, 7, 5, 6});
for(auto i : v)
cout<<i<<' ';
return 0;
}*/
