#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=3e5+10;
vector<pii>v[maxn];
int val[maxn];
vector<int>adj[maxn][2], qm[maxn];
int marc[maxn], rep[maxn];
vector<int>st;
vector<int>caras_scc[maxn];
void dfs(int u, int t, int cmp){
marc[u]++;
if(cmp!=-1){
for(int x : qm[u]) caras_scc[cmp].push_back(x);
}
for(int viz : adj[u][t]){
if(marc[viz]) continue;
dfs(viz,t,cmp);
}
if(t==0) st.push_back(u);
}
vector<int> find_reachable(vector<int> r, vector<int> a, vector<int> b, vector<int> c){
int n=r.size();
vector<int>ans(n);
for(int i=0;i<n;i++){
val[i]=r[i];
caras_scc[i].push_back(i);
}
for(int i=0;i<a.size();i++){
v[a[i]].push_back({b[i],c[i]});
v[b[i]].push_back({a[i],c[i]});
}
int at_n=n, qtd_scc=n;
auto kosaraju=[&](){
// cerr << "KOSARAJU\n";
vector<int>cor(n);
st.clear();
for(int i=0;i<qtd_scc;i++){
adj[i][0].clear(); adj[i][1].clear(); qm[i].clear(); marc[i]=0;
for(int x : caras_scc[i]){
qm[i].push_back(x);
rep[x]=i;
}
}
for(int i=0;i<qtd_scc;i++){
for(int x : caras_scc[i]) cor[val[x]]=1;
for(int x : caras_scc[i]){
for(pii p : v[x]){
if(cor[p.se]&&rep[p.fi]!=i){
// cerr << "aresta " << i << " -> " << p.fi << '\n';
adj[i][0].push_back(rep[p.fi]);
adj[rep[p.fi]][1].push_back(i);
}
}
}
for(int x : caras_scc[i]) cor[val[x]]=0;
caras_scc[i].clear();
}
int n_qtd_scc=0;
for(int i=0;i<qtd_scc;i++) if(!marc[i]) dfs(i,0,-1);
for(int i=0;i<qtd_scc;i++) marc[i]=0;
reverse(st.begin(),st.end());
for(int x : st){
if(!marc[x]){
dfs(x,1,n_qtd_scc);
n_qtd_scc++;
}
}
qtd_scc=n_qtd_scc;
};
while(true){
kosaraju();
if(at_n==qtd_scc) break;
at_n=qtd_scc;
}
int best=n;
vector<int>possib;
// cerr << "qtd_scc " << qtd_scc << '\n';
for(int i=0;i<qtd_scc;i++){
// cerr << "scc " << i << ": " << '\n';
// for(int x : qm[i]) cerr << x << ' ';
// cerr << '\n';
if(adj[i][0].size()==0){
if(best>qm[i].size()) best=qm[i].size(), possib.clear();
if(best==qm[i].size()){
for(int x : qm[i]) possib.push_back(x);
}
}
}
for(int x : possib) ans[x]=1;
return ans;
}
