#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") // codeforces
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") // yandex
#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
uint64_t steps = 0;
uint64_t steps_2 = 0;
struct Node{
int me = -2, next = -1;
};
// first node is sentinel
vector<Node> nodes{Node{-1, 0}};
struct Edge_Component{
int key;
vector<int> vertices;
};
vector<Edge_Component> edge_components;
template<typename T>
void join(vector<T> &a, vector<T> &b){
if(a.size() < b.size()){
a.swap(b);
}
steps_2 += b.size();
a.insert(a.end(), b.begin(), b.end());
b.clear();
}
void list_join(pair<int, int> &a, pair<int, int> b){
// 0, 0 is invalid empty list
if(a.first == 0 && a.second == 0){
a = b;
return;
}
nodes[a.second].next = b.first;
a.second = b.second;
}
struct Component{
vector<int> vertices;
unordered_set<int> keys;
unordered_map<int, int> edge_pos;
// pair<first_node, last_node>
unordered_map<int, pair<int, int> > reachable_edges;
unordered_map<int, pair<int, int> > unreachable_edges;
template<typename T>
bool search(T callback){
while(!reachable_edges.empty()){
auto it = reachable_edges.begin();
Node u = nodes[it->second.first];
while(u.me != -1){
auto p = u.me;
auto &pos = edge_pos[p];
auto const&vv = edge_components[p].vertices;
while(pos < (int)vv.size()){
if(callback(vv[pos])) return true;
++pos;
}
it->second.first = u.next;
u = nodes[u.next];
}
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];
list_join(v, w);
unreachable_edges.erase(c);
}
}
}
size_t size(){
return reachable_edges.size() + unreachable_edges.size() + keys.size() /*+edge_pos.size()*/;
}
void absorb(Component &o){
join(vertices, o.vertices);
for(auto &e:o.reachable_edges){
++steps;
list_join(reachable_edges[e.first], e.second);
}
for(auto &e:o.unreachable_edges){
++steps;
if(keys.count(e.first)){
list_join(reachable_edges[e.first], e.second);
} else {
list_join(unreachable_edges[e.first], e.second);
}
}
for(auto &e:o.keys){
++steps;
add_key(e);
}
if(edge_pos.size() < o.edge_pos.size()){
edge_pos.swap(o.edge_pos);
}
for(auto const&e:o.edge_pos){
++steps;
auto &f = edge_pos[e.first];
f = max(f, e.second);
}
}
};
struct DSU{
DSU(int n_) : n(n_), p(n, -1), comps(n){
}
int f(int x){
++steps_2;
return p[x] < 0 ? x : p[x] = f(p[x]);
}
Component& c(int x){
return comps[f(x)];
}
bool u(int a, int b){
++steps;
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) {
#ifdef LOCAL_RUN
auto time_a = chrono::high_resolution_clock::now();
#endif
const int m = u.size();
const int n = r.size();
unordered_map<int, vector<int> > c_inv;
c_inv.reserve(1<<10);
c_inv.max_load_factor(0.25);
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
vector<int> vert;
vert.reserve(n);
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){
++steps;
if(vis[u] == tim) return;
vis[u] = tim;
nodes.push_back(Node{tim, 0});
list_join(uni.comps[u].unreachable_edges[e.first], make_pair(nodes.size()-1, nodes.size()-1));
//edge_components.back().vertices.push_back(u);
vert.push_back(u);
for(auto const&e:g[u]){
rec(rec, e);
}
};
for(auto const&f:e.second){
++steps_2;
if(vis[u[f]] <= t0){
++tim;
vert.clear();
edge_components.push_back(Edge_Component{e.first});
rec(rec, u[f]);
edge_components.back().vertices = vert;
}
}
for(auto const&f:e.second){
g[u[f]].pop_back();
g[v[f]].pop_back();
}
}
#ifdef LOCAL_RUN
auto time_b = chrono::high_resolution_clock::now();
cerr << "tmp: " << chrono::duration_cast<chrono::nanoseconds>(time_b - time_a).count()*1e-9 << "\n";
#endif
for(int i=0; i<n; ++i){
uni.c(i).add_key(r[i]);
uni.c(i).vertices.push_back(i);
}
#ifdef LOCAL_RUN
auto time_c = chrono::high_resolution_clock::now();
cerr << "go search: " << chrono::duration_cast<chrono::nanoseconds>(time_c - time_b).count()*1e-9 << "\n";;
#endif
pair<int, vector<int> > out(n+1, {});
// run search
vis.assign(n, 0);
tim = 1;
vector<int> to(n, -1);
vector<int> prev(n, -1);
for(int i=0; i<n; ++i){
int a = uni.f(i);
++tim;
if(vis[a] == 0){
vis[a] = tim;
prev[a] = -1;
// 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;
prev[b] = a;
vis[b] = tim;
// continue search with b
a = b;
return true;
}
if(vis[b] == tim){
//cerr << "cycle " << a;
// extract cycle
int cnt = 0;
for(int c = b; c != a; c = to[c]){
//cerr << " " << c;
uni.u(a, c);
++cnt;
}
//cerr << "cycle: " << cnt << "\n";
const int aa = uni.f(a);
if(prev[b] != -1){
assert(to[prev[b]] == b);
to[prev[b]] = aa;
}
prev[aa] = prev[b];
a = aa;
//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;
//cerr << v.size() << " : ";
//for(auto &e : v) cerr << e << " ";
//cerr << "\n";
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;
}
#ifdef LOCAL_RUN
auto time_d = chrono::high_resolution_clock::now();
cerr << "done: " << chrono::duration_cast<chrono::nanoseconds>(time_d - time_c).count()*1e-9 << "\n";;
cerr << steps << "\n";
cerr << steps_2 << "\n";
#endif
return ret;
}
