#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
const int maxn=3*1e5+5;
vector<pair<int,int> > v[maxn];
void ae(int i,int j,int z)
{
v[i].push_back({j,z});
v[j].push_back({i,z});
}
int cnt,used[maxn];
int in[maxn];
int k[maxn];
int bg;
bool f;
vector<int> e[maxn], u;
int l[maxn],done[maxn];
int fl(int x)
{
if(l[x]==x)return x;
return l[x]=fl(l[x]);
}
void dfs(int i)
{
if(f)return;
int x=fl(i);
if(x!=bg)
{
//cout<<i<<" ! "<<bg<<endl;
f=1;
done[x]=1;
l[bg]=x;
return;
}
//cout<<i<<endl;
cnt++;
in[k[i]]=1;
used[i]=1;
u.push_back(i);
for(int j=0; j<e[k[i]].size(); j++)
{
int nb=e[k[i]][j];
if(used[nb])continue;
dfs(nb);
}
e[k[i]].clear();
for(int j=0; j<v[i].size(); j++)
{
pair<int,int> nb=v[i][j];
if(used[nb.first])continue;
if(in[nb.second])dfs(nb.first);
else
{
u.push_back(nb.second);
e[nb.second].push_back(nb.first);
}
}
}
vector<int> p;
void dfs1(int i)
{
if(fl(i)==bg)p.push_back(i);
//cout<<i<<endl;
cnt++;
in[k[i]]=1;
used[i]=1;
u.push_back(i);
for(int j=0; j<e[k[i]].size(); j++)
{
int nb=e[k[i]][j];
if(used[nb])continue;
dfs(nb);
}
e[k[i]].clear();
for(int j=0; j<v[i].size(); j++)
{
pair<int,int> nb=v[i][j];
if(used[nb.first])continue;
if(in[nb.second])dfs1(nb.first);
else
{
u.push_back(nb.second);
e[nb.second].push_back(nb.first);
}
}
}
std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C)
{
for(int i=0; i<R.size(); i++)
k[i]=R[i],l[i]=i;
for(int i=0; i<U.size(); i++)
ae(U[i],V[i],C[i]);
for(int j=0; j<=20; j++)
{
memset(done,0,sizeof(done));
for(int i=0; i<R.size(); i++)
{
if(done[i]||fl(i)!=i)continue;
//cout<<i<<"!"<<endl;
bg=i;
dfs(i);
for(int x=0;x<u.size();x++)
{
in[k[u[x]]]=used[u[x]]=0;
e[u[x]].clear();
}
u.clear();
f=0;
}
}
vector<int> ans;
int minn=R.size();
for(int i=0;i<R.size();i++)
{
if(fl(i)==i)
{
bg=i;
cnt=0;
dfs1(i);
if(cnt<minn)
{
minn=cnt;
ans=p;
}
else if(cnt==minn)
{
for(int j=0;j<p.size();j++)
ans.push_back(p[j]);
}
for(int x=0;x<u.size();x++)
{
in[k[u[x]]]=used[u[x]]=0;
e[u[x]].clear();
}
u.clear();
p.clear();
}
}
vector<int> h=ans;
ans.clear();
for(int i=0;i<R.size();i++)
ans.push_back(0);
for(int i=0;i<h.size();i++)
ans[h[i]]=1;
return ans;
}
