#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
const int maxn=3*1e5+5;
int k[maxn];
vector<pair<int,int> > v[maxn];
vector<int> e[maxn],u,ans;
int cnt,minn,used[maxn],act[maxn];
void clean()
{
for(int i=0; i<u.size(); i++)
{
int j=u[i];
used[j]=0;
act[k[j]]=0;
e[j].clear();
}
u.clear();
}
vector<int> p;
void bfs(int s)
{
clean();
p.clear();
cnt=0;
stack<int> q;
q.push(s);
used[s]=1;
act[k[s]]=1;
while(q.size())
{
cnt++;
int f=q.top();
q.pop();
p.push_back(f);
u.push_back(f);
for(int i=0; i<e[k[f]].size(); i++)
{
int nb=e[k[f]][i];
if(!used[nb])
{
used[nb]=1;
act[k[nb]]=1;
q.push(nb);
}
}
e[k[f]].clear();
for(int i=0; i<v[f].size(); i++)
{
pair<int,int> nb=v[f][i];
if(used[nb.first])continue;
if(act[nb.second])
{
used[nb.first]=1;
act[k[nb.first]]=1;
q.push(nb.first);
}
else
{
u.push_back(nb.second);
e[nb.second].push_back(nb.first);
}
}
}
if(cnt<minn)
{
minn=cnt;
ans=p;
}
else if(cnt==minn)
{
for(int i=0; i<p.size(); i++)
ans.push_back(p[i]);
}
}
int curr;
int done[maxn];
int l[maxn];
int par[maxn];
int sz[maxn];
int fl(int x)
{
if(x==l[x])return x;
return l[x]=fl(l[x]);
}
void bfs1(int s)
{
clean();
stack<int> q;
q.push(s);
used[s]=1;
act[k[s]]=1;
u.push_back(s);
while(q.size())
{
int f=q.top();
q.pop();
for(int i=0; i<e[k[f]].size(); i++)
{
int nb=e[k[f]][i];
if(!used[nb])
{
int x=fl(nb);
if(par[x]!=s)
{
//cout<<s<<" "<<x<<endl;
s=fl(s);
par[s]=par[x];
if(sz[x]>sz[s])swap(x,s);
done[par[x]]=curr;
l[s]=x;
sz[x]+=sz[s];
return;
}
u.push_back(nb);
used[nb]=1;
act[k[nb]]=1;
q.push(nb);
}
}
e[k[f]].clear();
for(int i=0; i<v[f].size(); i++)
{
pair<int,int> nb=v[f][i];
if(used[nb.first])continue;
if(act[nb.second])
{
int x=fl(nb.first);
if(par[x]!=s)
{
//cout<<s<<" "<<x<<endl;
s=fl(s);
par[s]=par[x];
if(sz[x]>sz[s])swap(x,s);
done[par[x]]=curr;
l[s]=x;
sz[x]+=sz[s];
return;
}
u.push_back(nb.first);
used[nb.first]=1;
act[k[nb.first]]=1;
q.push(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)
{
minn=R.size();
for(int i=0; i<R.size(); i++)
{
k[i]=R[i];
l[i]=i;
par[i]=i;
sz[i]=1;
}
for(int i=0; i<U.size(); i++)
{
v[U[i]].push_back({V[i],C[i]});
v[V[i]].push_back({U[i],C[i]});
}
for(int c=1; c<=18; c++)
{
curr=c;
for(int i=0; i<R.size(); i++)
{
if(par[fl(i)]==i&&done[i]!=curr)
{
bfs1(i);
}
}
}
for(int i=0; i<R.size(); i++)
if(par[fl(i)]==i)bfs(i);
vector<int> h(R.size());
for(int i=0; i<ans.size(); i++)
h[ans[i]]=1;
return h;
}
