#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
#pragma GCC optimize("Ofast")
const int N = 1e6 + 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];
vector<int> ans;
vector<int> pars;
int vis[N],timer = 0,vis2[N];
vector<pair<int,int>> edges;
void solve(int tim){
for(int i:pars){
if(bad[i]) continue;
set<int> add;
add.insert(i);
set<array<int,3>> bf;
timer++;
vis[i] = timer;
while(!add.empty()){
int v = (*add.begin());
vis2[c[v]] = timer;
add.erase(v);
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.insert(to);
}else{
bf.insert({w,v,to});
}
}
}
auto it = bf.lower_bound({c[v],0,0});
while(it != bf.end() && c[v] == (*it)[0]){
int u = (*it)[1],t = (*it)[2];
if(vis[t] != timer) add.insert((*it)[2]);
vis[t] = timer;
G[u].push_back(t);
GR[t].push_back(u);
edges.emplace_back(u,t);
it = bf.erase(it);
}
}
timer++;
vis[i] = timer;
queue<int> q;
q.push(i);
bool found = false;
while(!q.empty()){
int v = q.front();q.pop();
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){
p[get(v)] = get(to);
G[v].push_back(to);
GR[to].push_back(v);
edges.push_back({v,to});
found = true;
break;
}
}
if(found) break;
}
if(!found){
bad[i] = 1;
}
}
pars.clear();
for(int i = 0;i < n;i++){
if(get(i) == i){
pars.push_back(i);
}
}
}
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);
}
timer++;
for(int i = 0;i < n;i++){
if(vis[i] != timer){
dfs(i);
}
}
reverse(ord.begin(),ord.end());
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;
vector<int> comps;
for(int i = 1;i <= t;i++){
if(vis[i] == timer) continue;
if(sz[i] < mn){
mn = sz[i];
comps = vector<int> (1,i);
}else if(sz[i] == mn){
comps.push_back(i);
}
}
timer++;
for(int i:comps){
vis[i] = timer;
}
for(int i = 0;i < n;i++){
if(vis[comp[i]] == timer){
ans[i] = 1;
}
}
return ans;
}
