#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include "keys.h"
using namespace std;
const int MAX_N=3e5+5;
vector<pair<int,int>>g[MAX_N];
vector<int>wait[MAX_N];
bool taken[MAX_N];
bool keys[MAX_N];
queue<int>q;
int N;
vector<int>key;
int bfs(int s)
{
while(q.size())q.pop();
for(int i=0;i<N;i++){wait[i].clear();keys[i]=0;taken[i]=0;}
q.push(s);
while(q.size())
{
int u=q.front();
q.pop();
if(taken[u])continue;
taken[u]=1;
keys[key[u]]=1;
for(int v:wait[key[u]])q.push(v);
wait[key[u]].clear();
for(auto [v,c]:g[u])
{
if(keys[c])q.push(v);
else
{
wait[c].push_back(v);
}
}
}
int cnt=0;
for(int i=0;i<N;i++)
{
if(taken[i])cnt++;
}
return cnt;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c)
{
key=r;
N=r.size();
for(int i=0;i<u.size();i++)
{
g[u[i]].push_back({v[i],c[i]});
g[v[i]].push_back({u[i],c[i]});
}
int mi=1e9;
vector<int>minnodes;
for(int i=0;i<N;i++)
{
int cur=bfs(i);
if(cur<mi)
{
minnodes.clear();
minnodes.push_back(i);
mi=cur;
}
else if(cur==mi)minnodes.push_back(i);
}
vector<int>ans;
ans.resize(N);
for(int u:minnodes)ans[u]=1;
return ans;
}
