#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int M = 300'010;
vector<int> rep(M,1), sajz(M,1);
vector<set<int>> keys(M);
vector<map<int, vector<int>>> g(M);
vector<vector<int>> edges(M);
vector<int> vis(M);
int best = M;
stack<int> V;
vector<set<int>> adj(M);
int Find(int v) {
return rep[v]==v?v:rep[v]=Find(rep[v]);
}
int Union(int a, int b) {
// cout << a << " " << b << "\n";
a=Find(a);
b=Find(b);
int res = 1;
if(sajz[a] > sajz[b]) {
swap(a,b);
res = 0;
}
for(auto k : keys[a]) {
if(keys[b].find(k)==keys[b].end()) {
for(auto x : g[b][k]) edges[b].push_back(x);
}
keys[b].insert(k);
}
for(auto x : adj[a]) adj[b].insert(x);
for(auto x : edges[a]) edges[b].push_back(x);
rep[a] = b;
sajz[b] += sajz[a];
return res;
}
void dfs(int v) {
vis[v] = 1;
int cnt = 0;
V.push(v);
while(edges[v].size()) {
auto x = Find(edges[v].back()); edges[v].pop_back();
adj[v].insert(x);
if(vis[x]==2) continue;
else if(vis[x]==1) {
while(V.size() && V.top() != x) {
Union(V.top(), v);
V.pop();
}
Union(x, v);
vis[v] = 2;
v = Find(v);
V.push(v);
} else {
dfs(x);
}
}
vis[v] = 2;
}
vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> C) {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
for(int i=0; i<M; ++i) rep[i] =i;
int n = R.size();
int m = u.size();
for(int i=0; i<n; ++i) {
int x = R[i];
keys[i].insert(x);
}
for(int i=0; i<m; ++i) {
int a = u[i]; int b = v[i]; int c = C[i];
g[a][c].push_back(b);
g[b][c].push_back(a);
}
for(int i=0; i<n; ++i) {
for(auto k : keys[i]) for(auto x : g[i][k]) edges[i].push_back(x);
}
for(int i=0; i<n; ++i) rep[i] = i;
for(int i=0; i<n; ++i) {
if(vis[i]==0) dfs(i);
}
for(int i=0; i<n; ++i) {
adj[i].erase(i);
vector<int> to_del;
for(auto x : adj[i]) {
if(Find(x)==i) to_del.push_back(x);
}
for(auto x : to_del) adj[i].erase(x);
}
// for(int i=0; i<n; ++i) cout << Find(i) << " "; cout << "\n";
for(int i=0; i<n; ++i) if(adj[Find(i)].size()==0) {
best = min(best, sajz[Find(i)]);
// cout << Find(i) << "\n";
}
vector<int> ans(n);
for(int i=0; i<n; ++i) {
if(sajz[Find(i)]==best && adj[Find(i)].size()==0) ans[i] = 1;
}
return ans;
}
