#include <vector>
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 999'999;
int traverse(int start, vector<int> (&r), vector<vector<pii>> (&edges))
{
map<int, bool> has_access;
map<int, vector<int>> will_have_access;
int n = edges.size();
vector<bool> rooms_reached(n, 0);
queue<int> rooms_processed;
int ans = 1;
rooms_reached[start] = 1;
rooms_processed.push(start);
while (!rooms_processed.empty())
{
int room = rooms_processed.front();
rooms_processed.pop();
int new_key = r[room];
has_access[new_key] = 1;
for (int neigh: will_have_access[new_key])
{
if (rooms_reached[neigh] == 0)
{
rooms_reached[neigh] = 1;
rooms_processed.push(neigh);
ans++;
}
}
will_have_access[new_key] = {};
for (pii x: edges[room])
{
int neigh = x.first;
int required = x.second;
if (rooms_reached[neigh] == 0)
{
if (has_access[required])
{
rooms_reached[neigh] = 1;
rooms_processed.push(neigh);
ans++;
}
else
will_have_access[required].push_back(neigh);
}
}
}
return ans;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = r.size();
vector<vector<pii>> edges(n);
int m = u.size();
for (int i=0; i<m; i++)
{
int uu = u[i];
int vv = v[i];
int corridor = c[i];
edges[uu].push_back({vv, corridor});
edges[vv].push_back({uu, corridor});
}
vector<int> count_of_rooms_reached(n);
for (int i=0; i<n; i++)
count_of_rooms_reached[i] = traverse(i, r, edges);
int mini = INF;
for (int i=0; i<n; i++)
mini = min(mini, count_of_rooms_reached[i]);
vector<int> ans(n, 0);
for (int i=0; i<n; i++)
if (count_of_rooms_reached[i]==mini)
ans[i] = 1;
return ans;
}
