#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pp=pair<int, int>;
const int Nmax=200010;
int N, M, a, b, c, Cent, G[Nmax], S[Nmax], T[Nmax], P[Nmax], Sz[Nmax], ans[Nmax];
int A, B, C, ap, bp, cp;
bool visited[Nmax], chk[Nmax];
vector<int> adj[Nmax], mst[Nmax], V[Nmax], W[Nmax];
vector<pp> E;
int Find(int u) {return G[u]?G[u]=Find(G[u]):u;}
bool Union(int u, int v) {
u=Find(u), v=Find(v);
if(u==v) return false;
G[u]=v;
return true;
}
void DFS_Size(int curr, int prev) {
S[curr]=1;
for(int next:mst[curr]) if(next!=prev) {
DFS_Size(next, curr);
S[curr]+=S[next];
}
}
int DFS_Centroid(int curr, int prev) {
for(int next:mst[curr]) if(next!=prev) {
if(S[next]>N/2) return DFS_Centroid(next, curr);
}
return curr;
}
void DFS_Compress(int curr, int c) {
P[curr]=c, S[curr]=visited[curr]=1;
W[c].push_back(curr);
for(int next:mst[curr]) if(!visited[next]) {
DFS_Compress(next, curr);
S[curr]+=S[next];
}
}
void DFS_Compressed(int curr, int &sum) {
sum+=T[curr];
chk[curr]=1;
for(int next:V[curr]) if(!chk[curr]) DFS_Compressed(next, sum);
}
void DFS_DeleteCnt(int curr, int &cnt, int c) {
ans[curr]=c; cnt--;
if(!cnt) return;
for(int next:adj[curr]) if(!ans[next]) {
DFS_DeleteCnt(next, cnt, c);
if(!cnt) return;
}
}
void DFS_EraseSum(int curr, int &sum) {
chk[curr]=1;
sum+=T[curr];
for(int i:W[curr]) ans[i]=ap;
if(sum>=A) return;
for(int next:V[curr]) if(!chk[next]) DFS_EraseSum(next, sum);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N=n, M=p.size();
A=min({a, b, c}), C=max({a, b, c}), B=a+b+c-A-C;
ap=(a==A)?1:((b==A)?2:3), bp=(c==B)?3:((b==B)?2:1), cp=6-ap-bp;
for(int i=1; i<=M; i++) {
int u=p[i-1], v=p[i-1];
u++, v++;
adj[u].push_back(v);
adj[v].push_back(u);
E.push_back({u, v});
}
for(pp i:E) {
if(Union(i.x, i.y)) {
mst[i.x].push_back(i.y);
mst[i.y].push_back(i.x);
}
}
DFS_Size(1, 0);
Cent=DFS_Centroid(1, 0);
int cnt=0;
visited[Cent]=1;
for(int i:mst[Cent]) {
DFS_Compress(i, ++cnt);
if(S[i]>=A) {
int tmp=A;
ans[Cent]=2;
DFS_DeleteCnt(i, tmp, ap);
tmp=B;
DFS_DeleteCnt(Cent, tmp, bp);
vector<int> t;
for(int i=1; i<=N; i++) {
if(!ans[i]) ans[i]=cp;
t.push_back(ans[i]);
}
return t;
}
T[cnt]=S[i];
}
for(pp i:E) V[P[i.x]].push_back(P[i.y]);
for(int i=1; i<=cnt; i++) {
sort(V[i].begin(), V[i].end());
V[i].erase(unique(V[i].begin(), V[i].end()), V[i].end());
}
for(int i=1; i<=cnt; i++) if(!chk[i]) {
int siz=0;
DFS_Compressed(i, siz);
if(siz>=A) {
int sum=0;
fill(chk+1, chk+cnt+1, 0);
DFS_EraseSum(i, sum);
sum=B;
DFS_DeleteCnt(1, sum, bp);
vector<int> t;
for(int j=1; j<=N; j++) {
if(!ans[j]) ans[j]=cp;
t.push_back(ans[j]);
}
return t;
}
}
}
