#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long inf=1e18;
long long n,m,nm=0,a[300069],dsu[300069],cc[300069],dh[300069],mdh[300069],vtd2[300069],cc2[300069];
multiset<long long> ms[300069];
multiset<pair<long long,long long>> el[300069];
queue<long long> al[300069];
bitset<300069> vtd,spc;
pair<long long,long long> ed[600069];
long long fd(long long x)
{
if(dsu[x]!=x)
{
dsu[x]=fd(dsu[x]);
}
return dsu[x];
}
inline void jo(long long x,long long y)
{
long long k,l;
multiset<long long>::iterator it;
multiset<pair<long long,long long>>::iterator it2;
x=fd(x);
y=fd(y);
if(cc[y]>cc[x])
{
swap(x,y);
}
mdh[x]=min(mdh[x],mdh[y]);
vtd2[x]+=vtd2[y];
for(it=ms[y].begin();it!=ms[y].end();it++)
{
k=*it;
for(it2=el[x].lower_bound({k,0});it2!=el[x].end()&&it2->fr==k;)
{
al[x].push(it2->sc);
it2++;
el[x].erase(prev(it2));
}
ms[x].insert(k);
}
for(it2=el[y].begin();it2!=el[y].end();it2++)
{
k=it2->fr;
l=it2->sc;
if(ms[x].find(k)==ms[x].end())
{
el[x].insert(*it2);
}
else
{
al[x].push(l);
}
}
for(;!al[y].empty();al[y].pop())
{
al[x].push(al[y].front());
}
cc[x]+=cc[y];
dsu[y]=x;
}
void scc(long long x)
{
long long l;
vtd[x]=1;
vtd2[x]++;
mdh[x]=dh[x];
for(;!al[fd(x)].empty();)
{
l=al[fd(x)].front();
al[fd(x)].pop();
nm++;
ed[nm]={x,l};
if(!vtd[l])
{
dh[l]=dh[x]+1;
scc(l);
}
if(vtd2[fd(l)]&&mdh[fd(l)]<mdh[fd(x)])
{
jo(x,l);
}
}
vtd2[fd(x)]--;
}
vector<int> find_reachable(vector<int> oa,vector<int> ka,vector<int> la,vector<int> wg)
{
long long i,ii,k,l,w,mn=inf,z;
vector<int> v;
n=oa.size();
for(i=1;i<=n;i++)
{
a[i]=oa[i-1]+1;
dsu[i]=i;
cc[i]=1;
ms[i].insert(a[i]);
}
m=ka.size();
for(i=0;i<m;i++)
{
k=ka[i]+1;
l=la[i]+1;
w=wg[i]+1;
for(ii=0;ii<2;ii++)
{
if(a[k]!=w)
{
el[k].insert({w,l});
}
else
{
al[k].push(l);
}
cc[k]++;
swap(k,l);
}
}
for(i=1;i<=n;i++)
{
if(!vtd[i])
{
dh[i]=0;
scc(i);
}
}
for(i=1;i<=nm;i++)
{
k=ed[i].fr;
l=ed[i].sc;
if(fd(k)!=fd(l))
{
spc[fd(k)]=1;
}
}
for(i=1;i<=n;i++)
{
cc2[fd(i)]++;
}
for(i=1;i<=n;i++)
{
if(fd(i)==i&&!spc[i])
{
mn=min(mn,cc2[i]);
}
}
for(i=1;i<=n;i++)
{
z=cc2[fd(i)]==mn&&!spc[fd(i)];
v.push_back(z);
}
return v;
}
