#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
const int N = 4e5 + 1;
int n,c[N],p[N],m;
vector<pair<int,int>> g[N];
vector<int> G[N],GR[N];
int get(int v){
if(p[v] == v) return v;
return p[v] = get(p[v]);
}
void merge(int a,int b){
a = get(a);
b = get(b);
p[a] = b;
}
bool bad[N];
map<pair<int,int>,bool> blocked;
vector<int> ans;
vector<int> pars;
vector<pair<int,int>> st[N];
int vis[N],timer = 1,vis2[N];
vector<pair<int,int>> edges;
void solve(int tim){
vector<int> nv;
vector<pair<int,int>> bb;
for(int i:pars){
if(bad[i]) continue;
// cout << i << '\n';
if(tim == 0){
assert(G[i].empty());
}
queue<int> add;
add.push(i);
timer++;
vector<int>all;
vis[i] = timer;
while(!add.empty()){
int v = add.front();
vis2[c[v]] = timer;
// cout << v << ' ';
add.pop();
for(auto [to,w]:g[v]){
if(get(to) == i && vis[to] != timer){
if(vis2[w] == timer){
vis[to] = timer;
G[v].push_back(to);
GR[to].push_back(v);
edges.push_back({v,to});
add.push(to);
}else{
all.push_back(w);
st[w].push_back({v,to});
}
}
}
for(auto [u,t]:st[c[v]]){
if(vis[t] != timer) add.push(t);
vis[t] = timer;
G[u].push_back(t);
GR[t].push_back(u);
edges.push_back({u,t});
}
st[c[v]].clear();
}
for(int j:all){
st[j].clear();
}
timer++;
vis[i] = timer;
queue<int> q;
q.push(i);
bool found = false,BAD = false;
while(!q.empty()){
int v = q.front();q.pop();
// cout << v << ' ';
for(int to:G[v]){
if(vis[to] == timer) continue;
vis[to] = timer;
q.push(to);
}
for(auto [to,w]:g[v]){
if(get(v) != get(to) && vis2[w] == timer - 1){
bb.push_back({v,to});
BAD = 1;
found = true;
break;
}
}
if(found) break;
}
// cout << "|\n";
if(!found){
bad[i] = 1;
}else if(!BAD){
nv.push_back(i);
}
}
for(auto [v,to]:bb){
p[get(v)] = get(to);
G[v].push_back(to);
GR[to].push_back(v);
edges.push_back({v,to});
}
pars.swap(nv);
// cout << '\n';
}
int comp[N],sz[N];
vector<int> ord;
void dfs(int v){
vis[v] = timer;
for(int to:G[v]){
if(vis[to] == timer) continue;
dfs(to);
}
ord.push_back(v);
}
void dfs1(int v){
for(int to:GR[v]){
if(!comp[to]){
sz[comp[v]]++;
comp[to] = comp[v];
dfs1(to);
}
}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> C){
n = (int)r.size();m = (int)v.size();
ans.assign(n,0);
for(int i = 0;i < n;i++){
c[i] = r[i];
p[i] = i;
pars.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]});
}
for(int i = 0;i < 20;i++){
solve(i);
if(i == 0 && n > 2000) return ans;
}
for(int i = 0;i < n;i++){
g[i].clear();
}
timer++;
for(int i = 0;i < n;i++){
if(vis[i] != timer){
dfs(i);
}
}
reverse(ord.begin(),ord.end());
for(int i = 0;i < n;i++){
G[i].clear();
}
for(auto [x,y]:edges){
GR[y].push_back(x);
}
int t = 0;
for(int i:ord){
if(!comp[i]){
comp[i] = ++t;
sz[comp[i]] = 1;
dfs1(i);
}
}
timer++;
for(auto [x,y]:edges){
if(comp[x] != comp[y]){
vis[comp[x]] = timer;
}
}
int mn = 1e9;
for(int i = 1;i <= t;i++){
if(vis[i] == timer) continue;
mn = min(mn,sz[i]);
}
for(int i = 0;i < n;i++){
if(vis[comp[i]] != timer && sz[comp[i]] == mn){
ans[i] = 1;
}
}
return ans;
}
