#include "split.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(0);
vector<int>adj[100100],adj2[100100];
bitset<100100>vis;
int sz[100100],THEONE,treep[100100];
vector<int>ans;
int OK(int k,int a,int b,int c){
sz[k]=1;
vis[k]=1;
for(auto i:adj[k]) if(!vis[i]){
treep[i]=k;
if(OK(i,a,b,c)) return 1;
sz[k]+=sz[i];
}
if(a<=sz[k]&&sz[k]<=b+c)
return THEONE=k,1;
return 0;
}
void gendfstree(int n){
vis[n]=1;
for(auto i:adj[n])
if(!vis[i]) gendfstree(i),
adj2[n].push_back(i),
adj2[i].push_back(n);
}
void docol(int n,int p,int &CC,int col){
if(!CC) return;
ans[n]=col,CC--;
for(auto x:adj2[n])
if(x-p)docol(x,n,CC,col);
}
void genans(int k,int a,int b,int c,int A,int B,int C){
for(auto&i:ans)i=C;
vis.reset();
gendfstree(k);
int n=a+b+c;
if(sz[THEONE]>=b)
swap(a,b),swap(A,B);
docol(THEONE,treep[THEONE],a,A);
docol(treep[THEONE],THEONE,b,B);
assert(!a&&!b);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
ans.resize(n);
vector<int> res;
int m=p.size();
for(int i=0;i<m;i++)
adj[p[i]].push_back(q[i]),
adj[q[i]].push_back(p[i]);
int A=1,B=2,C=3;
if(a>b)swap(a,b),swap(A,B);
if(b>c)swap(b,c),swap(B,C);
if(a>b)swap(a,b),swap(A,B);
vector<int>v(n);
iota(v.begin(),v.end(),0);
shuffle(v.begin(),v.end(),rng);
int CC=3e7/p.size();
while(CC--){
for(int i=0;i<n;i++)
shuffle(adj[i].begin(),adj[i].end(),rng);
int i=rng()%n;
vis.reset();
if(OK(i,a,b,c)){
genans(i,a,b,c,A,B,C);
break;
}
}
return ans;
}
