#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define lb lower_bound
const int N=1000006, INF=1e9+7;
int p[N], p2[N], f[N];
vector<vi> Ans;
struct abc{
set<pii> s;
set<int> k;
queue<int> d;
int pa;
vi v;
int sz;
} e[N];
void add_key(int x, int c){
auto &[s, k, d, pa, v, sz] = e[x];
if(k.find(c)!=k.end()) return;
k.insert(c);
for (auto it = s.lb({c,0}); it != s.lb({c,INF}); it=s.lb({c, 0}))
d.push((*it).second), s.erase(it);
}
void add_door(int x, int y, int c){
auto &[s, k, d, pa, v, sz] = e[x];
if(k.find(c)!=k.end()) d.push(y);
else s.insert({c, y});
}
int P(int x){ return (p[x]<0) ? x : p[x] = P(p[x]); }
int sz(int x){ return -P(x); }
void unite(int x, int y){
if((x=P(x))==(y=P(y)))return;
if(sz(x)<sz(y))swap(x, y);
p[x]+=p[y];
p[y]=x;
}
int P2(int x){ return (p2[x]<0) ? x : p2[x] = P2(p2[x]); }
int sz2(int x){ return -P2(x); }
void unite2(int x, int y){
if((x=P2(x))==(y=P2(y)))return;
if(sz2(x)<sz2(y))swap(x, y);
p2[x]+=p2[y];
p2[y]=x;
}
void un(int x, int y){
int PA=e[y].pa;
unite2(x, y);
if(e[x].sz<e[y].sz)swap(e[x], e[y]);
if(P2(x)==y)swap(e[x], e[y]), swap(x, y);
auto &[xs, xk, xd, xpa, xv, xsz]=e[x];
auto &[ys, yk, yd, ypa, yv, ysz]=e[y];
for (auto [k,Y]:ys) add_door(x, Y, k);
for (auto k:yk) add_key(x, k);
while(!yd.empty()) xd.push(yd.front()), yd.pop();
xpa=PA;
for (auto Y:yv) xv.pb(Y);
xsz=xv.size();
}
void next(int x, int w=-1){
int X=P2(x), PA;
auto &[s, k, d, pa, v, sz]=e[X];
if(!d.empty()){
pa=d.front();
d.pop();
PA=P2(pa);
while(PA==X && !d.empty()){
pa=d.front();
d.pop();
PA=P2(pa);
}
}
if(pa==-1 || PA==X){
Ans.pb(v);
f[P(X)]=1;
return;
}
if(P(X)==P(PA)){
while(PA!=X)un(X, PA), X=P2(x), PA=P2(e[X].pa);
e[X].pa=-1;
next(X);
}else{
if(f[P(PA)])f[P(X)]=1;
unite(X, PA);
}
}
vi find_reachable(vi r, vi u, vi v, vi c) {
vi ans(r.size(), 0);
int n=r.size(), m=u.size();
vector<pii> V[n];
for (int i=0; i<m; i++){
int x=u[i], y=v[i], k=c[i];
V[x].pb({y, k});
V[y].pb({x, k});
}
for (int i=0; i<n; i++){
p[i]=p2[i]=-1;
for (auto[y,c]:V[i])e[i].s.insert({c, y});
add_key(i, r[i]);
e[i].pa=-1;
e[i].v.pb(i);
e[i].sz=1;
}
for (int i=0; i<n; i++)
if(f[P(i)]==0 && e[P2(i)].pa==-1)next(i);
int an=INF;
for (auto v:Ans)an=min(an, (int)v.size());
for (auto v:Ans){
if(an<v.size())continue;
for (auto x:v) ans[x]=1;
}
return ans;
}
