#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;
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 Chk3[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;
Chk3[now]=true;
for(int nxt : v[now]) if(!Chk3[nxt] && res[nxt]==typ)
{
cnt=dfs3(nxt, cnt, typ);
}
return cnt;
}
void make3()
///color 3 when res is made out of 1 and 2
{
init_uf();
for(pii ele : E) if(res[ele.fir]==res[ele.sec]) onion(ele.fir, ele.sec);
int root1, root2;
for(int i=0;i<N;i++)
{
if(res[i]==1) root1=i;
else root2=i;
}
/*for(int i=0;i<N;i++)
{
if(res[i]==1) assert(findpar(i)==findpar(root1));
else assert(findpar(i)==findpar(root2));
}*/
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-A)
{
int ncol=(comp[0].sec<=N-B ? 1 : 2);
if(comp[0].fir==pre)
{
for(int nxt : child[now])
{
if(reach[nxt]>=disc[now]) color(nxt, now, 3-ncol);
else color(nxt, now, ncol);
}
color(pre, now, ncol);
res[now]=3-ncol;
}
else
{
color(comp[0].fir, now, ncol);
color(now, comp[0].fir, 3-ncol);
}
make3();
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);
if(comp[0].fir!=pre)
{
for(int nxt : child[now]) if(reach[nxt]<disc[now]) dfs1(nxt, now, now);
}
}
for(int nxt : child[now]) if(par[nxt]==nxt) dfs2(nxt, 0);
}
int cnt[mxN]; ///각 정점별 가중치
vector <int> new_v[mxN]; /// 2-connected graph에서 간선 저장
vector <pii> new_E;
bool new_Chk[mxN];
int new_par[mxN];
int new_0;
vector <int> new_child[mxN];
int new_dep[mxN]; ///depth for dividing back edge
int new_deg[mxN];
vector<vector<int>> ear;
vector <int> cont[mxN];
void dfs4(int now)
{
new_Chk[now]=true;
for(int nxt : new_v[now]) if(!new_Chk[nxt])
{
new_child[now].push_back(nxt);
new_par[nxt]=now;
new_dep[nxt]=new_dep[now]+1;
dfs4(nxt);
}
}
typedef struct cmp1{
bool operator()(pii a, pii b)
{
int p=min(new_dep[a.fir], new_dep[a.sec]), q=min(new_dep[b.fir], new_dep[b.sec]);
return p<q;
}
}cmp1;
bool path_Chk[2*mxN];
vector <int> walk;
void f(int idx, int st)
{
path_Chk[idx]=true;
if(ear[idx][0]!=st) reverse(ear[idx].begin(), ear[idx].end());
for(int i=1;i+1<ear[idx].size();i++)
{
walk.push_back(ear[idx][i]);
for(int ele : cont[ear[idx][i]]) if(!path_Chk[ele]) f(ele, ear[idx][i]);
}
}
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;
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;
else if(sub[child[0][0]]<=N-A)
{
int ncol=(sub[child[0][0]]<=N-B ? 1 : 2);
color(child[0][0], 0, ncol);
color(0, child[0][0], 3-ncol);
make3();
return res;
}
else
{
for(int i=1;i<child[0].size();i++) dfs1(child[0][i], 0, 0);
}
}
dfs2(0, -1);
if(ok!=0) return res;
for(int i=0;i<N;i++)
{
cnt[findpar(i)]++;
}
for(pii ele : E)
{
int p=findpar(ele.fir), q=findpar(ele.sec);
if(p==q) continue;
new_v[p].push_back(q);
new_v[q].push_back(p);
new_E.emplace_back(p, q);
}
for(int i=0;i<N;i++) if(new_v[i].size())
{
sort(new_v[i].begin(), new_v[i].end());
new_v[i].erase(unique(new_v[i].begin(), new_v[i].end()), new_v[i].end());
}
for(int i=0;i<N;i++) new_deg[i]=new_v[i].size();
new_0=findpar(0);
new_par[new_0]=-1;
dfs4(new_0);
priority_queue <pii, vector<pii>, cmp1> pq;
for(pii ele : new_E)
{
if(new_dep[ele.fir]>new_dep[ele.sec]) swap(ele.fir, ele.sec);
if(new_dep[ele.fir]!=new_dep[ele.sec]-1)
{
pq.push(ele);
}
}
while(!pq.empty())
{
pii now=pq.top();
pq.pop();
vector <int> path;
path.push_back(now.fir);
path.push_back(now.sec);
new_deg[now.fir]--; new_deg[now.sec]--;
int pos=now.sec;
while(new_deg[pos]==1)
{
new_deg[pos]--;
pos=new_par[pos];
new_deg[pos]--;
path.push_back(pos);
}
ear.push_back(path);
}
/*printf("ear");
for(vector <int> ve : ear)
{
for(int ele : ve) printf("%d ", ele);
printf("\n");
}*/
for(int i=0;i+1<ear.size();i++)
{
cont[ear[i][0]].push_back(i);
cont[ear[i].back()].push_back(i);
}
cont[ear[ear.size()-1][0]].push_back(ear.size()-1);
for(int i=0;i<N;i++) if(cont[i].size()) sort(cont[i].begin(), cont[i].end());
int wstart=ear[ear.size()-1][0];
walk.push_back(wstart);
for(int ele : cont[wstart]) f(ele, wstart);
/*printf("walk\n");
for(int ele : walk) printf("%d\n", ele);*/
int sum=0;
int new_cnt=0;
for(int i=0;i<N;i++) if(findpar(i)==i) new_cnt++;
assert(new_cnt==walk.size());
for(int i=0;i<walk.size();i++)
{
sum+=cnt[walk[i]];
if(sum>=A)
{
for(int j=0;j<=i;j++) res[walk[j]]=1;
for(int j=i+1;j<walk.size();j++) res[walk[j]]=2;
break;
}
}
//for(int i=0;i<N;i++) printf("par[%d]=%d\n", i, findpar(i));
for(int i=0;i<N;i++) if(findpar(i)!=i) res[i]=res[findpar(i)];
make3();
return res;
}
/*15 18
5 5 6
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 0
0 8
8 9
9 10
10 3
9 11
11 6
0 12
12 13
12 14
13 14*/
