#include<bits/stdc++.h>
using namespace std;
struct DSU {
int n;
vector<int> p;
DSU(int _n) : n(_n) {
p.resize(n);
iota(p.begin(),p.end(),0);
}
int get(int x){
return x ^ p[x] ? get(p[x]) : p[x] = x;
}
void unite(int a, int b){
a = get(a), b = get(b);
p[a] = b;
}
};
struct info {
map<int,vector<int>> blo;
set<int> unl;
};
vector<info> inf;
vector<int> vis;
bool step(vector<int> &r, vector<vector<pair<int,int>>> &gr, DSU &d){
bool ok = 0;
int n = r.size();
vis.clear();
vis.resize(n,0);
queue<pair<int,int>> Q;
for(int i = 0; i < n; ++i){
if(i == d.get(i))Q.push({i,i});
}
while(Q.size()){
auto x = Q.front();
Q.pop();
if(x.second != d.get(x.second))continue;
if(d.get(x.first) != x.second){
ok = 1;
d.unite(x.second,x.first);
continue;
}
if(vis[x.first])continue;
vis[x.first] = 1;
for(auto y : gr[x.first]){
if(inf[x.second].unl.count(y.second))Q.push({y.first,x.second});
else inf[x.second].blo[y.second].push_back(y.first);
}
inf[x.second].unl.insert(r[x.first]);
for(auto y : inf[x.second].blo[r[x.first]])Q.push({y,x.second});
inf[x.second].blo[r[x.first]].clear();
}
return ok;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
int n = r.size();
int m = u.size();
inf.resize(n);
DSU d(n);
vector<vector<pair<int,int>>> gr(n);
for(int i = 0; i < m; ++i){
gr[u[i]].push_back({v[i],c[i]});
gr[v[i]].push_back({u[i],c[i]});
}
while(step(r,gr,d));
vector<int> nsiz(n,0);
int mn = n+1;
for(int i = 0; i < n; ++i){
if(vis[i])nsiz[d.get(i)]++;
}
for(int i = 0; i < n; ++i){
mn = min(mn,nsiz[d.get(i)]);
}
for(int i = 0; i < n; ++i){
if(mn != nsiz[d.get(i)])vis[i] = 0;
}
return vis;
}
