#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
int n, maxC;
vector<int> par;
vector<int> sz;
vector<vector<list<int>>> g;
vector<vector<bool>> keys;
int find(int u){
if(u == par[u]) return u;
else return par[u] = find(par[u]);
}
void merge(int a, int b){
a = find(a);
b = find(b);
if(a == b) return;
par[b] = a;
sz[a] += sz[b];
for(int i = 0; i < maxC; i++) g[a][i].splice(g[a][i].begin(), g[b][i]);
}
vector<int> state;
stack<int> st;
void dfs(int u){
u = find(u);
st.push(u);
state[u] = 1;
bool ok = true;
for(int i = 0; i < maxC; i++){
if(!keys[u][i]) continue;
while(!g[u][i].empty()){
int v = g[u][i].back();
g[u][i].pop_back();
v = find(v);
if(state[v] == 0) ok = false, dfs(v);
else if(state[v] == 1){
int w;
do
{
w = st.top();
st.pop();
merge(u, w);
}while(w != v);
dfs(u);
return;
}
else{
sz[u] = INF;
state[u] = 2;
return;
}
}
}
if(!ok) sz[u] = INF;
state[u] = 2;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n = (int)r.size();
maxC = 0;
for(int i : r) maxC = max(maxC, i);
for(int i : c) maxC = max(maxC, i);
maxC++;
par.resize(n);
sz.assign(n, 1);
for(int i = 0; i < n; i++) par[i] = i;
g.assign(n, vector<list<int>>(maxC));
for(int i = 0; i < (int)u.size(); i++){
g[u[i]][c[i]].push_back(v[i]);
g[v[i]][c[i]].push_back(u[i]);
}
keys.assign(n, vector<bool>(maxC));
for(int i = 0; i < n; i++) keys[i][r[i]] = true;
state.resize(n);
for(int i = 0; i < n; i++){
if(state[i] == 0) dfs(i);
}
int best = INF;
vector<int> good;
for(int i = 0; i < n; i++){
int j = find(i);
if(sz[j] < best){
best = sz[j];
good.clear();
}
if(sz[j] == best) good.push_back(i);
}
vector<int> ans(n);
for(int i : good) ans[i] = 1;
return ans;
}
