#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
int n, mn=INT_MAX/2;
vector<bool> key, visited, die;
vector<int> vect, ans, dsu, in;
vector<vector<int> > nokey;
vector<vector<pii> > graph;
int fp(int a){
if (dsu[a]==-1)return a;
return dsu[a]=fp(dsu[a]);
}
void merge(int a, int b){
a=fp(a), b=fp(b);
if (a!=b)dsu[a]=b;
}
void reset(){
for (auto a:in)visited[a]=key[vect[a]]=0, nokey[a].clear();
in.clear();
}
void bfs(int start){
queue<int> q;
q.push(start);
key[vect[start]]=1;
while (q.size()){
int node=q.front();
q.pop();
if (fp(node)!=fp(start)){
merge(start, node);
reset();
return;
}
if (visited[node])continue;
visited[node]=1;
in.pb(node);
for (auto num:graph[node])if (!visited[num.fi]){
if (key[num.se]){
q.push(num.fi);
if (!key[vect[num.fi]])for (auto a:nokey[vect[num.fi]])q.push(a), key[vect[a]]=1;
key[vect[num.fi]]=1;
}
else nokey[num.se].pb(num.fi);
}
}
die[start]=1;
if (in.size()<mn)mn=in.size(), ans=in;
else if (in.size()==mn)for (auto a:in)ans.pb(a);
reset();
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
n=r.size();
vect=r;
die.resize(n, 0);
key.resize(n, 0);
visited.resize(n, 0);
nokey.resize(n);
graph.resize(n);
dsu.resize(n, -1);
for (int i=0; i<u.size(); ++i){
graph[u[i]].pb(mp(v[i], c[i]));
graph[v[i]].pb(mp(u[i], c[i]));
}
bool loop=1;
while (loop){
loop=0;
for (int i=0; i<n; ++i)if (fp(i)==i&&!die[i]){
bfs(i);
loop=1;
}
}
for (int i=0; i<n; ++i)bfs(i);
vector<int> res(n, 0);
for (auto a:ans)res[a]=1;
return res;
}
