#include <bits/stdc++.h>
using namespace std;
struct Edge_Compoment{
int key;
vector<int> vertices;
};
vector<Edge_Compoment> edge_components;
template<typename T>
void join(vector<T> &a, vector<T> &b){
if(a.size() < b.size()){
swap(a, b);
}
a.insert(a.end(), b.begin(), b.end());
b.clear();
}
struct Component{
struct PP{
int name;
int pos;
};
vector<int> vertices;
unordered_set<int> keys;
unordered_map<int, vector<PP> > reachable_edges;
unordered_map<int, vector<PP> > unreachable_edges;
template<typename T>
bool search(T callback){
while(!reachable_edges.empty()){
auto it = reachable_edges.begin();
while(!it->second.empty()){
auto&p = it->second.back();
auto&vv = edge_components[p.name].vertices;
while(p.pos < (int)vv.size()){
if(callback(vv[p.pos])) return true;
++p.pos;
}
it->second.pop_back();
}
reachable_edges.erase(it);
}
return false;
}
void add_key(int c){
if(!keys.count(c)){
keys.insert(c);
if(unreachable_edges.count(c)){
auto &v = reachable_edges[c];
auto &w = unreachable_edges[c];
v.insert(v.end(), w.begin(), w.end());
unreachable_edges.erase(c);
}
}
}
size_t size(){
return reachable_edges.size() + keys.size() + vertices.size();
}
void absorb(Component &o){
join(vertices, o.vertices);
for(auto &e:o.reachable_edges){
join(reachable_edges[e.first], e.second);
}
for(auto &e:o.unreachable_edges){
join(unreachable_edges[e.first], e.second);
}
for(auto &e:o.keys){
add_key(e);
}
}
};
struct DSU{
DSU(int n_) : n(n_), p(n, -1), comps(n){
}
int f(int x){
return p[x] < 0 ? x : f(p[x]);
}
Component& c(int x){
return comps[f(x)];
}
bool u(int a, int b){
a = f(a);
b = f(b);
if(a == b) return false;
if(comps[a].size() < comps[b].size()){
swap(a, b);
}
comps[a].absorb(comps[b]);
p[b] = a;
return true;
}
int n;
vector<int> p;
vector<Component> comps;
};
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
const int m = u.size();
const int n = r.size();
map<int, vector<int> > c_inv;
for(int i=0; i<m; ++i){
c_inv[c[i]].push_back(i);
}
DSU uni(n);
// find edge components
edge_components.clear();
vector<vector<int> > g(n);
vector<int> vis(n, -1);
int tim = -1; // = index of last edge_component
for(auto const&e:c_inv){
for(auto const&f:e.second){
g[u[f]].push_back(v[f]);
g[v[f]].push_back(u[f]);
}
const int t0 = tim;
auto rec = [&](auto rec, int u){
if(vis[u] == tim) return;
vis[u] = tim;
uni.comps[u].unreachable_edges[e.first].push_back({tim, 0});
edge_components.back().vertices.push_back(u);
for(auto const&e:g[u]){
rec(rec, e);
}
};
for(auto const&f:e.second){
if(vis[u[f]] <= t0){
++tim;
edge_components.push_back(Edge_Compoment{e.first});
rec(rec, u[f]);
}
}
for(auto const&f:e.second){
g[u[f]].pop_back();
g[v[f]].pop_back();
}
}
for(int i=0; i<n; ++i){
uni.c(i).add_key(r[i]);
uni.c(i).vertices.push_back(i);
}
pair<int, vector<int> > out(n+1, {});
// run search
vis.assign(n, 0);
tim = 1;
vector<int> to(n, -1);
for(int i=0; i<n; ++i){
int a = uni.f(i);
++tim;
if(vis[a] == 0){
vis[a] = tim;
// find out edge
for(;;){
auto res = uni.comps[a].search([&](int const&v){
//cerr << " => " << v << "\n";
const int b = uni.f(v);
if(b == a) return false; // loop
if(vis[b] == 0){
//cerr << "move to: " << b << "\n";
to[a] = b;
vis[b] = tim;
// continue search with b
a = b;
return true;
}
if(vis[b] == tim){
//cerr << "cycle " << a;
// extract cycle
for(int c = b; c != a; c = to[c]){
//cerr << " " << c;
uni.u(a, c);
}
a = uni.f(a);
//cerr << " -> " << a << "\n";
to[a] = -1;
assert(vis[a] == tim);
return true;
}
// found old vertices -> finish
//cerr << "old " << b << "\n";
a = -1;
return true;
});
if(a == -1) break; // found old vertices
if(!res){
auto const&v = uni.comps[a].vertices;
if((int)v.size() < out.first){
out.first = v.size();
out.second.clear();
}
if((int)v.size() == out.first){
out.second.insert(out.second.end(), v.begin(), v.end());
}
break;
}
}
}
}
vector<int> ret(n);
for(auto const&e:out.second){
ret[e] = 1;
}
return ret;
}
