#include <bits/stdc++.h>
#include "keys.h"
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<int,int>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long
using namespace std ;
const int maxn = 3e5 + 10 , inf = 1e9+ 10 , mod = 998244353;
int par[maxn] , mark[maxn] , C[maxn] , t[maxn] , ans[maxn];
int mp[maxn] ;
int find(int v){
if(par[v] == v)return v;
return par[v] = find(par[v]);
}
void mrg(int v, int u){
v = find(v) ; u = find(u);
if(v==u){
return;
}
mp[u] |= mp[v] ;
par[v] = u ;
return;
}
vector <int> tp , Gr[maxn] , G[maxn];
void dfs(int v){
mark[v] = 1;
for(int u : G[v]){
if(mark[u] == 1)continue ;
dfs(u);
}
tp.pb(v);
}
int cnt =0;
void dfs2(int v){
mark[v] =1;
C[v] = cnt;
for(int u : Gr[v]){
if(mark[u] == 1)continue;
dfs2(u) ;
}
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c){
int n = sz(r)-1 ;
int m = sz(u)-1 ;
rep(i ,0 , n)par[i] = i ;
rep(i ,0 ,n)mp[i] = (1<<r[i]) ;
int ted =0 ;
while(1){
ted++;
rep(i ,0 , n){
G[i].clear() ;
Gr[i].clear() ;
mark[i] =0 ;
}
rep(i , 0 ,m){
if(find(v[i]) == find(u[i]))continue ;
if(mp[find(u[i])]>>c[i]&1){
G[find(u[i])].pb(find(v[i])) ;
}
if(mp[find(v[i])]>>c[i]&1){
G[find(v[i])].pb(find(u[i])) ;
}
}
rep(i , 0 ,n){
for(int u : G[i]){
Gr[u].pb(i) ;
}
}
tp.clear();
rep(i ,0 , n){
if(mark[i] == 1)continue;
dfs(i);
}
reverse(all(tp));
rep(i , 0 ,n)mark[i] = 0;
cnt =0 ;
for(int v : tp){
if(mark[v] == 1){
continue ;
}
dfs2(v);
cnt++ ;
}
bool ok = 0 ;
rep(v , 0 ,n){
for(int u : G[v]){
if(C[v] == C[u]){
mrg(v,u) ;
ok =1 ;
}
}
}
if(ok == 0 || ted==40){
rep(i ,0 , n)t[find(i)]++;
int mn = n+1;
rep(i , 0 ,n){
if(find(i) != i)continue ;
if(sz(G[i]) == 0){
mn = min(mn , t[i]);
}
}
rep(i , 0 ,n){
if(t[find(i)] == mn && sz(G[find(i)])==0){
ans[i] =1 ;
}
}
break ;
}
}
vector <int> vec;
rep(i , 0 ,n){
vec.pb(ans[i]);
}
return vec;
}
