#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 300001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
int par[MAXN], vis[MAXN], p[MAXN];
vector<int> et, x[MAXN], a[MAXN];
int root(int v){
if(par[v] == v) return v;
par[v] = root(par[v]);
return par[v];
}
void join(int v, int u){
v = root(v), u = root(u);
par[u] = v;
p[v] += p[u];
for(auto & i : x[u])
x[v].append(i);
}
void dfs(int v){
vis[v]++;
et.append(v);
for(auto & i : a[v]){
if(vis[i] == 2) p[root(v)]++;
else if(vis[i] == 1){
int u = root(i);
while(et.back() != u){
join(u, et.back());
et.pop_back();
}
p[u]--;
}
else{
p[root(v)]++;
dfs(i);
}
}
vis[v]++;
if(et.back() == v) et.pop_back();
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
int n, m, ans, ver;
vector<int> vec;
n = r.size(), m = v.size();
for(int i = 0; i < n; i++){
par[i] = i;
x[i] = {i};
}
for(int i = 0; i < m; i++){
if(r[u[i]] == c[i])
a[u[i]].append(v[i]);
if(r[v[i]] == c[i])
a[v[i]].append(u[i]);
}
ans = n + 1;
for(int i = 0; i < n; i++)
if(!vis[i]) dfs(i);
for(int i = 0; i < n; i++){
ver = root(i);
if(p[ver]) continue;
if(ans > x[ver].size()){
ans = x[ver].size();
vec.clear();
}
if(ans == x[ver].size())
for(auto & j : x[ver])
vec.append(j);
}
vector<int> answer(n, 0);
for(auto & i : vec)
answer[i] = 1;
return answer;
}
