#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast")
// #define int long long
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 5e5+10;
const int MAXA = 5e4+10;
const int SQRT = 300;
const int INF = 1e9;
const int MOD = 998244353;
const int LOG = 20;
int n, a[MAXN];
vector<pii> adj[MAXN];
struct dsu {
int par[MAXN];
void bd(){
for(int i=1; i<=n; i++) par[i] = i;
}
int f(int x){
return (par[x]==x ? x : par[x]=f(par[x]));
}
void mer(int x, int y){
x = f(x); y = f(y);
if(x==y) return;
par[x] = y;
}
} DSU;
int day, key[MAXN], vis[MAXN], emp[MAXN];
vector<int> can;
vector<int> vec[MAXN];
int bfs(int sta, bool ty){
set<int> rev;
queue<int> q; q.push(sta);
vis[sta] = day;
while(!q.empty()){
int nw = q.front(); q.pop();
if(DSU.f(nw) != DSU.f(sta)){
for(auto wei : rev) vec[wei].clear();
return nw;
}
if(ty) can.pb(nw);
if(key[a[nw]] != day){
for(auto in : vec[a[nw]]){
if(vis[in] == day) continue;
q.push(in);
vis[in] = day;
}
}
key[a[nw]] = day;
// if(sta == 3) cout << nw << " nw\n";
for(auto [nx, wei] : adj[nw]){
// if(sta==3) cout << nx << ' '<< wei << " wei\n";
if(vis[nx] == day) continue;
if(key[wei] == day){
// bisa
q.push(nx);
vis[nx] = day;
} else {
// blm bisa
rev.insert(wei);
vec[wei].pb(nx);
}
}
// if(sta==3) cout << "Done\n";
}
for(auto wei : rev) vec[wei].clear();
return -1;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
n = r.size();
for(int i=1; i<=n; i++) a[i] = r[i-1]+1;
for(int i=0; i<u.size(); i++){
adj[u[i]+1].pb({v[i]+1, c[i]+1});
adj[v[i]+1].pb({u[i]+1, c[i]+1});
}
DSU.bd();
vector<pii> pend;
do {
pend.clear();
for(int i=1; i<=n; i++){
if(DSU.f(i) == i){
day++;
int x = bfs(i, 0);
if(x != -1){
// cout << i << ' '<< x << " ix\n";
pend.pb({i,x});
}
}
}
for(auto [x, y] : pend) DSU.mer(x, y);
// cout << "Done\n";
} while(!pend.empty());
vector<int> opt; int mn = INF;
for(int i=1; i<=n; i++){
if(DSU.f(i) == i){
can.clear();
day++;
bfs(i, 1);
// cout << i << ' '<<can.size()<<" mn\n";
// for(auto in : can) cout << in << ' ';
// cout << " in\n";
if(can.size() < mn){
mn = can.size(); opt.clear();
}
if(can.size() == mn){
for(auto in : can) opt.pb(in);
}
}
}
std::vector<int> ans(n, 0);
for(auto in : opt) ans[in-1] = 1;
return ans;
}
