// Be Name Khoda //
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x) x.begin(), x.end()
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const int maxn5 = 3e5 + 10;
set <int> key[maxn5];
set <pair<int, int>> ed[maxn5];
vector <int> edge[maxn5], av[maxn5];
vector <pair<int, int>> adj[maxn5];
int cmp[maxn5], r[maxn5], mark[maxn5];
bool bad[maxn5];
int merge(int a, int b){
if(av[a].size() < av[b].size())
swap(a, b);
//cout << "here merging " << a << ' ' << b << endl;
for(auto u : av[b]){
cmp[u] = a;
av[a].pb(u);
key[r[u]].insert(a);
for(auto it = ed[r[u]].lower_bound(mp(a, -1)); it != ed[r[u]].end() && (it -> fi) == a;){
auto itt = it;
it++;
edge[a].pb(itt -> se);
ed[r[u]].erase(itt);
}
for(auto [v, c] : adj[u]){
if(key[c].find(a) != key[c].end())
edge[a].pb(v);
else
ed[c].insert({a, v});
}
}
av[b].clear();
av[b].shrink_to_fit();
return a;
}
bool dfs(int v){
mark[v] = 1;
//debug(v);
while(edge[v].size()){
int u = edge[v].back();
u = cmp[u];
//cout << "here is " << v << ' ' << u << ' ' << mark[u] << endl;
edge[v].pop_back();
if(u == v)
continue;
if(mark[u] == 0){
if(dfs(u)){
v = merge(v, cmp[u]);
mark[v] = 1;
}
else{
bad[v] = true;
mark[v] = 2;
return false;
}
}
else if(mark[u] == 1){
edge[v].pb(u);
return true;
}
else{
bad[v] = true;
mark[v] = 2;
return false;
}
}
mark[v] = 2;
return false;
}
std::vector<int> find_reachable(std::vector<int> R, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = R.size();
for(int i = 0; i < n; i++){
r[i] = R[i];
key[r[i]].insert(i);
cmp[i] = i;
av[i].pb(i);
}
for(int i = 0; i < int(u.size()); i++){
adj[u[i]].pb({v[i], c[i]});
adj[v[i]].pb({u[i], c[i]});
if(r[u[i]] == c[i])
edge[u[i]].pb(v[i]);
if(r[v[i]] == c[i])
edge[v[i]].pb(u[i]);
ed[c[i]].insert({v[i], u[i]});
ed[c[i]].insert({u[i], v[i]});
}
for(int i = 0; i < n; i++)
adj[i].shrink_to_fit();
for(int i = 0; i < n; i++) if(!mark[i])
dfs(i);
int mn = n;
vector <int> good;
for(int i = 0; i < n; i++) if(cmp[i] == i && !bad[i]){
//cout << "ha " << i << ' ' << av[i].size() << endl;
if(int(av[i].size()) < mn){
good.clear();
good = av[i];
mn = av[i].size();
}
else if(int(av[i].size()) == mn)
for(auto u : av[i])
good.pb(u);
}
vector <int> ret;
ret.resize(n);
fill(all(ret), 0);
for(auto u : good)
ret[u] = true;
return ret;
}
