#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
long long n,m,ttl=0,nn=0,dsu[200069],dh[100069],pg[100069],sbt[300069],wg[100069],pr[100069],fh[100069],ca[100069],sq[100069];
pair<long long,long long> d[3],mdh[100069];
vector<pair<long long,long long>> al[100069];
bitset<300069> vtd;
bitset<100069> vtd2,spc;
vector<long long> al2[300069],sbl[300069],al3[100069];
multiset<long long> ms[100069];
bool bad=0,r0=0;
long long fd(long long x)
{
if(dsu[x]!=x)
{
dsu[x]=fd(dsu[x]);
}
return dsu[x];
}
void bct(long long x,long long b4)
{
long long i,sz=al[x].size(),l,p;
vtd[x]=1;
vtd2[x]=1;
mdh[x]={dh[x],-1};
for(i=0;i<sz;i++)
{
l=al[x][i].fr;
p=al[x][i].sc;
if(p==b4)
{
continue;
}
if(!vtd[l])
{
dh[l]=dh[x]+1;
pg[x]=p;
bct(l,p);
}
if(vtd2[l])
{
dsu[fd(p)]=fd(pg[l]);
mdh[x]=min(mdh[x],{dh[l],p});
}
else if(mdh[l].fr<=dh[x])
{
dsu[fd(p)]=fd(mdh[l].sc);
mdh[x]=min(mdh[x],{mdh[l].fr,p});
}
}
vtd2[x]=0;
}
void bd(long long x)
{
long long i,sz=al2[x].size(),l,e=-1;
vtd[x]=1;
sbt[x]=x<n;
for(i=0;i<sz;i++)
{
l=al2[x][i];
if(!vtd[l])
{
bd(l);
sbt[x]+=sbt[l];
}
else
{
e=l;
}
}
for(i=0;i<sz;i++)
{
l=al2[x][i];
if(l!=e)
{
sbl[x].push_back(sbt[l]);
}
else
{
sbl[x].push_back(n-sbt[x]);
}
}
}
void trv(long long x,long long xx)
{
long long i,sz=al[x].size(),l;
vtd[x]=1;
if(d[xx].fr)
{
sq[x]=d[xx].sc;
d[xx].fr--;
}
for(i=0;i<sz;i++)
{
l=al[x][i].fr;
if((!wg[l]||spc[l]==spc[x])&&!vtd[l])
{
trv(l,xx);
}
}
}
void dbd(long long x,long long b4)
{
long long i,sz=al[x].size(),l,p,mn=dh[x];
vtd[x]=1;
vtd2[x]=1;
fh[x]=dh[x];
for(i=0;i<sz;i++)
{
l=al[x][i].fr;
p=al[x][i].sc;
if(p==b4)
{
continue;
}
if(wg[l])
{
if(!vtd[l])
{
dh[l]=dh[x]+1;
pr[l]=x;
dbd(l,p);
fh[x]=min(fh[x],fh[l]);
al3[x].push_back(l);
ms[x].insert(fh[l]);
}
else if(vtd2[l])
{
fh[x]=min(fh[x],dh[l]);
al3[l].push_back(x);
mn=min(mn,dh[l]);
}
}
}
vtd2[x]=0;
ms[x].insert(mn);
}
bool cmp(long long x,long long y)
{
return dh[x]>dh[y];
}
void dtrv(long long x)
{
long long i,sz=al3[x].size(),l;
vtd[x]=1;
ttl+=wg[x];
spc[x]=1;
if(ttl>=d[0].fr)
{
r0=1;
return;
}
nn++;
ca[nn]=x;
sort(al3[x].begin(),al3[x].end(),cmp);
for(i=0;i<sz;i++)
{
l=al3[x][i];
if(!vtd[l]&&(fh[l]>=dh[x]||dh[l]==dh[x]+1))
{
dtrv(l);
if(r0)
{
return;
}
}
}
nn--;
if(pr[x]+1)
{
ms[pr[x]].erase(ms[pr[x]].find(fh[x]));
if(!vtd[pr[x]]&&(!nn||*ms[pr[x]].begin()>dh[ca[nn]]))
{
dtrv(pr[x]);
}
}
}
vector<int> find_split(int on,int od,int od2,int od3,vector<int> ka,vector<int> la)
{
long long i,j,ii,l,w,sz,p,e;
vector<long long> v;
vector<int> v2;
n=on;
d[0]={od,1};
d[1]={od2,2};
d[2]={od3,3};
sort(d,d+3);
m=ka.size();
for(i=0;i<m;i++)
{
al[ka[i]].push_back({la[i],i});
al[la[i]].push_back({ka[i],i});
dsu[i]=i;
}
bct(0,-1);
for(i=0;i<m;i++)
{
for(ii=0;ii<2;ii++)
{
al2[ka[i]].push_back(n+fd(i));
al2[n+fd(i)].push_back(ka[i]);
swap(ka[i],la[i]);
}
}
for(i=0;i<n+m;i++)
{
sort(al2[i].begin(),al2[i].end());
v.clear();
sz=al2[i].size();
for(j=0;j<sz;j++)
{
l=al2[i][j];
if(!j||l!=al2[i][j-1])
{
v.push_back(l);
}
}
al2[i]=v;
}
vtd.reset();
bd(0);
for(i=n;i<n+m;i++)
{
sz=al2[i].size();
for(j=0;j<sz;j++)
{
l=al2[i][j];
w=sbl[i][j];
for(ii=0;ii<2;ii++)
{
if(w>=d[ii].fr&&n-w>=d[!ii].fr)
{
p=l;
e=ii;
break;
}
}
if(ii<2)
{
break;
}
}
if(j<sz)
{
vtd.reset();
for(j=0;j<sz;j++)
{
l=al2[i][j];
vtd[l]=l!=p;
}
trv(p,e);
vtd.reset();
vtd[p]=1;
trv(al2[i][al2[i][0]==p],!e);
bad=1;
break;
}
}
if(!bad)
{
for(i=n;i<n+m;i++)
{
if(fd(i-n)==i-n)
{
sz=al2[i].size();
for(j=0;j<sz;j++)
{
w=sbl[i][j];
if(n-w<d[1].fr)
{
break;
}
}
if(j>=sz)
{
for(j=0;j<sz;j++)
{
l=al2[i][j];
w=sbl[i][j];
wg[l]=w;
}
vtd.reset();
dh[l]=0;
pr[l]=-1;
dbd(l,-1);
vtd.reset();
dtrv(al3[l][al3[l].size()-1]);
e=ttl<d[0].fr||n-ttl<d[1].fr;
vtd.reset();
for(ii=0;ii<2;ii++)
{
for(j=0;j<sz;j++)
{
l=al2[i][j];
if(spc[l]==!ii)
{
trv(l,ii^e);
break;
}
}
}
bad=1;
break;
}
}
}
}
for(i=0;i<n;i++)
{
if(bad&&!sq[i])
{
sq[i]=d[2].sc;
}
v2.push_back(sq[i]);
}
return v2;
}
