#include "split.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
#define pii pair<int, int>
const int mxN=100010;
using namespace std;
int N, A, B, C, cp;
vector <pii> abc; ///크기순 정렬
vector <int> res;
vector <int> v[mxN]; ///간선
vector <pii> E; ///간선
int disc[mxN], tim, reach[mxN]; ///articulation point 찾을 때 사용
bool art[mxN]; ///cut vertex
vector <int> child[mxN], treev[mxN]; ///spanning tree while dfs
int sub[mxN]; ///size of subtree
int par[mxN]; ///uf
void init_uf(){for(int i=0;i<N;i++) par[i]=i;}
int findpar(int a){return (par[a]==a ? a : par[a]=findpar(par[a]));}
void onion(int a, int b){int p=findpar(a), q=findpar(b); par[p]=q;}
void dfs0(int now)
{
disc[now]=++tim;
reach[now]=tim;
sub[now]=1;
for(int nxt : v[now])
{
if(!disc[nxt])
{
child[now].push_back(nxt);
treev[now].push_back(nxt); treev[nxt].push_back(now);
dfs0(nxt);
if(reach[nxt]>=disc[now] && now!=0) art[now]=true;
reach[now]=min(reach[now], reach[nxt]);
sub[now]+=sub[nxt];
}
else
{
reach[now]=min(reach[now], disc[nxt]);
}
}
}
void color(int now, int pre, int col) ///colors subtree of now which its parent is pre with color col
{
res[now]=col;
for(int nxt : treev[now]) if(nxt!=pre) color(nxt, now, col);
}
void dfs1(int now, int pre, int parent) ///merge child of now to parent
{
par[now]=parent;
for(int nxt : treev[now]) if(par[nxt]==nxt && nxt!=pre) dfs1(nxt, now, parent);
}
bool Chk[mxN];
int dfs3(int now, int cnt, int typ)
///color 3 to make cnt[1]=A, cnt[2]=B
{
if(cnt>0) cnt--;
else res[now]=3;
Chk[now]=true;
for(int nxt : v[now]) if(!Chk[nxt] && res[nxt]==typ)
{
cnt=dfs3(nxt, cnt, typ);
}
return cnt;
}
void make3()
///color 3 when res is made out of 1 and 2
{
int root1, root2;
for(int i=0;i<N;i++)
{
if(res[i]==1) root1=i;
else root2=i;
}
dfs3(root1, A, 1);
dfs3(root2, B, 2);
for(int i=0;i<N;i++) res[i]=abc[res[i]-1].sec;
}
int ok;
void dfs2(int now, int pre)
///merge adjacent component from articulation point
{
if(ok!=0) return;
if(now==0 || !art[now])
{
for(int nxt : child[now]) if(par[nxt]==nxt) dfs2(nxt, 0);
return;
}
vector <pii> comp;
comp.emplace_back(pre, N-sub[now]);
for(int i=0;i<child[now].size();i++)
{
if(reach[child[now][i]]>=disc[now]) comp.emplace_back(child[now][i], sub[child[now][i]]);
else comp[0].sec+=sub[child[now][i]];
}
sort(comp.begin(), comp.end(), [](pii a, pii b){return a.sec>b.sec;});
if(comp[0].sec<A)
{
ok=-1; return;
}
else if(comp[0].sec<=N-B)
{
if(comp[0].fir==pre)
{
for(int nxt : child[now])
{
if(reach[nxt]>=reach[now]) color(nxt, now, 1);
else color(nxt, now, 2);
}
color(pre, now, 1);
res[now]=2;
}
else
{
color(comp[0].fir, now, 1);
color(now, comp[0].fir, 2);
}
make3();
int cnt3=0;
for(int i=0;i<N;i++) if(res[i]==3) cnt3++;
assert(cnt3==cp);
ok=1; return;
}
else
{
for(int i=1;i<comp.size();i++) if(par[comp[i].fir]==comp[i].fir) dfs1(comp[i].fir, now, now);
}
for(int nxt : child[now]) if(par[nxt]==nxt) dfs2(nxt, 0);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N=n;
res.resize(n);
for(int i=0;i<n;i++) res[i]=0;
abc.emplace_back(a, 1);
abc.emplace_back(b, 2);
abc.emplace_back(c, 3);
sort(abc.begin(), abc.end());
A=abc[0].fir; B=abc[1].fir; C=abc[2].fir; cp=c;
for(int i=0;i<p.size();i++)
{
v[p[i]].push_back(q[i]);
v[q[i]].push_back(p[i]);
E.emplace_back(q[i], p[i]);
}
dfs0(0);
init_uf();
if(child[0].size()>=2) art[0]=true;
if(art[0])
{
sort(child[0].begin(), child[0].end(), [](int x, int y){return sub[x]>sub[y];});
if(sub[child[0][0]]<A) return res;
if(sub[child[0][0]]>=A && sub[child[0][0]]<=N-B)
{
color(child[0][0], 0, 1);
color(0, child[0][0], 2);
make3();
int cnt3=0;
for(int i=0;i<N;i++) if(res[i]==3) cnt3++;
assert(cnt3==c);
return res;
}
else
{
for(int i=1;i<child[0].size();i++) dfs1(child[0][i], 0, 0);
}
}
dfs2(0, -1);
return res;
}
