#include <bits/stdc++.h>
#define __DEBUG__
#define pb push_back
using namespace std;
constexpr static int SIZE = 300000;
vector<array<int, 2>> g[SIZE];
set<array<int, 2>> pending_edges;
int visited[SIZE];
int keys[SIZE];
int counts[SIZE];
vector<int> r;
int min_count = INT_MAX;
int current_node;
void dfs(int node)
{
counts[current_node]++;
visited[node] = current_node;
int key = r[node];
if (keys[key] != current_node)
{
keys[key] = current_node;
array<int, 2> sss = {key, 0};
for (auto it = pending_edges.lower_bound(sss); it != pending_edges.end() && (*it)[0] == key; it++)
if (visited[(*it)[1]] != current_node)
dfs((*it)[1]);
}
for (auto [c, k] : g[node])
{
if (visited[c] == current_node)
continue;
if (keys[k] == current_node)
dfs(c);
else
pending_edges.insert({k, c});
}
}
vector<int> find_reachable(vector<int> rr, vector<int> u, vector<int> v, vector<int> c)
{
r = rr;
int n = r.size(), m = u.size();
for (int i = 0; i < m; i++)
{
g[v[i]].pb({u[i], c[i]});
g[u[i]].pb({v[i], c[i]});
}
int min_count = n;
for (int i = 0; i < n; i++)
{
visited[i] = -1;
keys[i] = -1;
}
for (int i = 0; i < n; i++)
{
current_node = i;
pending_edges.clear();
dfs(i);
min_count = min(min_count, counts[i]);
}
vector<int> res(n, 0);
for (int i = 0; i < n; i++)
if (counts[i] == min_count)
res[i] = 1;
return res;
}
