#include <bits/stdc++.h>
#define N 300005
using namespace std;
int group[N];
int find(int a){
if(a == group[a])return a;
return group[a] = find(group[a]);
}
bool merge(int a,int b){
a = find(a);
b = find(b);
if(a == b)
return 0;
group[a] = b;
return 1;
}
int low[N];
int tin[N];
bool is_bridge[2*N];
int vis[N];
bool vis2[N];
bool nowkeys[N];
vector<int> key[N];
vector<int> edges[N];
vector<pair<int,int>> adj[N];
vector<int> adj0[N];
int timer;
int tmp = -1;
void dfs(int v,int par){
tin[v] = timer++;
low[v] = tin[v];
vis[v] = tmp;
for(auto u:adj[v]){
if(u.first == par){
continue;
}
if(vis[u.second] != -1){
is_bridge[u.first] = 1;
if(vis[u.second] != vis[v]){
is_bridge[u.first] = 1;
}
else low[v] = min(low[v],tin[u.second]);
continue;
}
dfs(u.second,u.first);
if(low[u.second] > tin[v]){
is_bridge[u.first] = 1;
}
low[v] = min(low[v],low[u.second]);
}
}
void dfs2(int v){
vis2[v] = 1;
for(auto u:adj[v]){
if(is_bridge[u.first])continue;
merge(v,u.second);
if(vis2[u.second])continue;
dfs2(u.second);
}
}
int sz[N];
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<int> p(n,0);
for(int i = 0;i<m;i++){
adj0[u[i]].push_back(i);
adj0[v[i]].push_back(i);
}
for(int i = 0;i<n;i++){
group[i] = i;
}
for(int x = 0;x<2;x++){
for(int i = 0;i<n;i++){
key[i].clear();
edges[i].clear();
adj[i].clear();
vis[i] = -1;
vis2[i] = 0;
sz[i] = 0;
nowkeys[i] = 0;
}
for(int i = 0;i<2*m;i++){
is_bridge[i] = 0;
}
for(int i = 0;i<n;i++){
key[find(i)].push_back(r[i]);
for(auto x:adj0[i]){
edges[find(i)].push_back(x);
}
}
for(int i = 0;i<n;i++){
if(i != find(i))continue;
for(auto x:key[i]){
nowkeys[x] = 1;
}
for(auto x:edges[i]){
if(nowkeys[c[x]]){
if(find(u[x]) != i)
adj[i].push_back({x,find(u[x])});
if(find(v[x]) != i)
adj[i].push_back({x+m,find(v[x])});
}
}
for(auto x:key[i]){
nowkeys[x] = 0;
}
}
timer = 0;
for(int i = 0;i<n;i++){
if(vis[i] == -1 && i == find(i)){
tmp = i;
dfs(i,-1);
}
}
for(int i = 0;i<n;i++){
if(i == find(i) && !vis2[i]){
dfs2(i);
}
}
for(int i = 0;i<n;i++){
sz[find(i)]++;
}
int mini = 1e9;
for(int i = 0;i<n;i++){
if(sz[i] && adj[i].empty())
mini = min(mini,sz[i]);
}
for(int i = 0;i<n;i++){
if(sz[find(i)] == mini && adj[find(i)].empty()){
p[i] = 1;
}
else p[i] = 0;
}
}
return p;
}
