#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 3e5 + 10;
int n, m, r[maxn], comp[maxn], st[maxn];
vector<pii> g[maxn];
int ans = maxn;
vector<int> res, ver[maxn], rej[maxn];
bool vis[maxn], bad[maxn], mark[maxn], expand;
void merge(int u, int v){
bool flg = true;
if ((u = comp[u]) == (v = comp[v])) return;
// debug(u, v);
if (ver[u].size() < ver[v].size()){
swap(u, v);
flg = !flg;
}
for (auto x: ver[v]){
if (x == v) continue;
comp[x] = u;
ver[u].push_back(x);
}
if (flg) st[u] = st[v];
comp[v] = u;
ver[u].push_back(v);
// debug(u, st[u]);
}
void dfs(int v){
// debug("dfs", v);
vis[v] = true;
mark[r[v]] = true;
while(!rej[r[v]].empty() && !expand){
int u = rej[r[v]].back();
rej[r[v]].pop_back();
if (bad[u]){
int x = comp[v];
for (auto y: ver[x]){
bad[y] = true;
}
expand = true;
return;
}
else if (comp[u] != comp[v]){
merge(v, u);
expand = true;
return;
}
else if (!vis[u]) dfs(u);
}
for (auto [u, w]: g[v]){
if (expand) return;
if (!mark[w]){
rej[w].push_back(u);
continue;
}
if (bad[u]){
int x = comp[v];
for (auto y: ver[x]){
bad[y] = true;
}
expand = true;
return;
}
else if (comp[u] != comp[v]){
merge(v, u);
expand = true;
return;
}
else if (!vis[u]) dfs(u);
}
}
vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
n = R.size();
m = C.size();
for (int i = 0; i < n; i++){
r[i] = R[i];
comp[i] = i;
st[i] = i;
ver[i].push_back(i);
}
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]});
}
bool flg = true;
int cnt = 1;
while (flg){
// debug(cnt);
cnt++;
flg = false;
memset(vis, false, sizeof vis);
for (int i = 0; i < n; i++){
int v = st[comp[i]];
if (!vis[v] && !bad[v]){
for (auto x: ver[comp[i]]) vis[x] = false;
expand = false;
// debug(v);
dfs(v);
// debug(expand);
if (!expand){
vector<int> tmp;
for (auto x: ver[comp[i]]){
bad[x] = true;
if (vis[x]) tmp.push_back(x);
}
if (tmp.size() < ans){
ans = tmp.size();
res.clear();
}
if (tmp.size() == ans){
for (auto x: tmp) res.push_back(x);
}
}
else{
flg = true;
}
v = comp[v];
for (auto x: ver[v]){
mark[r[x]] = false;
for (auto [u, w]: g[x]){
rej[w].clear();
}
}
}
}
}
vector<int> answer(n, 0);
for (auto x: res) answer[x] = 1;
return answer;
}
