#include <bits/stdc++.h>
using namespace std;
struct node {
set<int> key;
set<pair<int,int>> adj;
bool dead = false;
};
const int maxn = 2e5 + 5, INF = 1e9;
int n, m;
node info[maxn];
int fa[maxn];
int vis[maxn];
int rt(int u) {
if (fa[u]==u) return u;
else return fa[u] = rt(fa[u]);
}
void merge(int u, int v) {
if (info[u].key.size() + info[u].adj.size() > info[v].key.size() + info[v].adj.size()) swap(u, v);
for (int x:info[u].key) info[v].key.insert(x);
for (pair<int,int> x:info[u].adj) info[v].adj.insert(x);
fa[u] = v;
}
bool dfs(int u) {
bool done = true;
while (done) {
done = false;
u = rt(u);
vis[u] = 1;
for (int k:info[u].key) {
pair<int,int> cur;
int v;
while (true) {
cur = *info[u].adj.lower_bound(make_pair(k, 0));
if (cur.first!=k) break;
v = rt(cur.second);
if (u==v) {info[u].adj.erase(cur); continue;}
else break;
}
if (cur.first!=k) continue;
// cout << u << " " << v << endl;
if (vis[v]==2) {info[u].dead = true; return false;}
if (vis[v]==1) {merge(u, v); return true;}
if (dfs(v)) {
v = rt(v);
if (rt(u) == v) {done = true; break;}
else {merge(rt(u), v); return true;}
} else {
info[u].dead = true;
return false;
}
}
}
vis[u] = 2;
return false;
}
vector<int> find_reachable(vector<int> r, vector<int> U, vector<int> V, vector<int> C) {
n = r.size();
for (int i=0;i<n;i++){
info[i].key.insert(r[i]);
fa[i] = i;
info[i].adj.insert({INF, INF});
}
int m = U.size();
for (int i=0;i<m;i++) {
info[U[i]].adj.insert({C[i], V[i]});
info[V[i]].adj.insert({C[i], U[i]});
}
for (int i=0;i<n;i++) if (!vis[i]) dfs(i);
// for (int i=0;i<n;i++) cout << rt(i) << " "; cout << endl;
int sz[n];
for (int i=0;i<n;i++) sz[i] = 0;
for (int i=0;i<n;i++) if (!info[rt(i)].dead) {
sz[rt(i)]++;
}
int mn = INF;
for (int i=0;i<n;i++) if (!info[rt(i)].dead) {
mn = min(sz[rt(i)], mn);
}
vector<int> ans(n, 0);
for (int i=0;i<n;i++) ans[i] = (!info[rt(i)].dead && sz[rt(i)]==mn);
return ans;
}
