#include <bits/stdc++.h>
using namespace std;
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size();
int m = u.size();
vector <vector<pair<int,int>>> g(n);
for (int i = 0; i < m; i++) {
g[u[i]].emplace_back(v[i],c[i]);
g[v[i]].emplace_back(u[i],c[i]);
}
vector <int> par(n);
iota(par.begin(),par.end(),0);
function<int(int)> getpar = [&](int x) {
if (par[x] == x) return x;
return par[x] = getpar(par[x]);
};
auto unionset = [&](int a, int b) {
a = getpar(a);
b = getpar(b);
if (a == b) return;
par[b] = a;
};
vector <vector<int>> aa;
vector <int> dead(n,0);
vector <int> used(n,-1);
vector <vector<int>> b(n);
vector <int> t(n,-1);
int mn = n+1;
for (int i = 0; i < n; i++) {
if (getpar(i) != i || dead[i] == 1) continue;
vector <int> a;
vector <int> usedk;
queue <int> q;
q.push(i);
used[i] = i;
usedk.emplace_back(r[i]);
t[r[i]] = i;
bool merged = 0;
while (!q.empty()) {
int f = q.front();
q.pop();
a.emplace_back(f);
if (getpar(f) != i) {
merged = 1;
unionset(f,i);
break;
}
if (t[r[f]] != i) {
t[r[f]] = i;
usedk.emplace_back(r[f]);
for (auto res:b[r[f]]) {
if (used[res]==i) continue;
used[res] = i;
q.push(res);
}
b[r[f]].clear();
}
for (auto [to,k]:g[f]) {
if (used[to] == i) continue;
if (t[k] == i) {
used[to] = i;
q.push(to);
continue;
}
if (b[k].empty()) usedk.emplace_back(k);
b[k].emplace_back(to);
}
}
for (auto k:usedk) b[k].clear();
if (!merged) {
dead[i] = 1;
if (mn > a.size()) {
aa = {a};
mn = a.size();
} else if (mn == a.size()) {
aa.emplace_back(a);
}
}
}
vector<int> ans(n, 0);
for (auto a:aa) {
for (auto x:a) {
ans[x] = 1;
}
}
return ans;
}
