/* Ignut
started: 16.08.2024
now: 16.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████ ████████████████████████████████
██████████████████████████████ ██████████████████████████████
██████ ██████████████████ ██████████████████ ██████
██████ ██████████████ ██████████████ ██████
██████ ██ ████████████ ████████████ ██ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ██████ ██████
██████ ██████ ██████████ ██████████ ██████ ██████
██████ ██████ ████████ ████████ ██████ ██████
██████ ██████ ██████ ██████ ██████ ██████
██████ ████ ████ ████ ████ ██████
██████ ██████████ ████ ██████████ ██████
██████ ██ ██████ ████████ ██████ ██ ██████
██████ ██████ ████████ ██████ ██████
██████ ██ ██ ██████
██████████████████████ ████ ████ ██████████████████████
████████████████████████ ██ ██ ████████████████████████
██████████████████████████ ██████████████████████████
██████████████████████████████ ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5 + 123;
int n;
vector<int> r;
vector<pair<int, int>> g[N];
bool haveKey[N];
bool used[N];
vector<int> edges[N];
int BFS(int st) {
for (int i = 0; i < n; i ++) {
haveKey[i] = used[i] = false;
edges[i].clear();
}
queue<int> q;
q.push(st);
used[st] = true;
while (!q.empty()) {
int v = q.front(); q.pop();
int k = r[v];
if (!haveKey[k]) {
haveKey[k] = true;
for (int to : edges[k]) {
if (!used[to]) {
used[to] = true;
q.push(to);
}
}
edges[k].clear();
}
for (auto [to, c] : g[v]) {
if (used[to]) continue;
if (!haveKey[c]) {
edges[c].push_back(to);
}
else {
used[to] = true;
q.push(to);
}
}
}
int res = 0;
for (int i = 0; i < n; i ++) res += used[i];
return res;
}
vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
r = R;
n = R.size();
int m = U.size();
for (int i = 0; i < m; i ++) {
g[U[i]].push_back({V[i], C[i]});
g[V[i]].push_back({U[i], C[i]});
}
int min_p = n;
vector<int> res;
for (int i = 0; i < n; i ++) {
res.push_back(BFS(i));
min_p = min(min_p, res.back());
}
for (int i = 0; i < n; i ++) res[i] = (res[i] == min_p);
return res;
}
