#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 400005;
struct disj{
int pa[MAXN];
void init(){
iota(pa, pa + MAXN, 0);
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
pa[q] = p; return 1;
}
}disj;
vector<int> bycmp[MAXN];
set<int> keys[MAXN];
set<pi> gph[MAXN];
int comp[MAXN], nxt[MAXN];
int find(int x){
return comp[x] = (comp[x] == x ? x : find(comp[x]));
}
void merge_to(int u, int v){
u = find(u);
if(u == v) return;
comp[u] = v;
for(auto &i : keys[u]) keys[v].insert(i);
for(auto &i : gph[u]) gph[v].insert(i);
keys[u].clear();
gph[u].clear();
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = sz(r);
for(int i = 0; i < n; i++) keys[i].insert(r[i]);
for(int i = 0; i < sz(u); i++){
gph[u[i]].emplace(c[i], v[i]);
gph[v[i]].emplace(c[i], u[i]);
}
disj.init();
iota(comp, comp + MAXN, 0);
vector<int> ans(n, 1e9);
for(int i = 0; i < n; i++){
nxt[i] = i;
for(auto &[j, w] : gph[i]){
if(r[i] == j){
nxt[i] = w;
}
}
}
if(count(all(ans), 1) != 0) return ans;
for(int i = 0; i < n; i++){
if(find(i) != i) continue;
if(i == find(nxt[i])) continue;
if(!disj.uni(i, nxt[i])){
for(int j = find(nxt[i]); find(j) != find(n); j = find(nxt[j])){
merge_to(j, n);
}
disj.uni(i, n);
auto it = gph[n].begin();
nxt[n] = n;
while(it != gph[n].end()){
int k, v;
tie(k, v) = *it;
if(keys[n].find(k) != keys[n].end()){
if(find(v) == find(n)) it = gph[n].erase(it);
else{
nxt[n] = find(v);
break;
}
} else it++;
}
n++;
}
}
for(int j = 0; j < sz(ans); j++){
bycmp[find(j)].push_back(j);
}
fill(all(ans), 1e9);
for(int j = 0; j < n; j++){
if(sz(bycmp[j]) && find(nxt[j]) == find(j)){
for(auto &i : bycmp[j]){
if(i < sz(ans)) ans[i] = sz(bycmp[j]);
}
}
}
int val = *min_element(all(ans));
for(auto &i : ans){
i = (i == val);
}
return ans;
}
