#include "keys.h"
#include <iostream>
#include <vector>
#include <set>
#define cerr if(false)cerr
using namespace std;
using vi = vector<int>;
const int N = 300'005;
set<int>keys[N];
set<pair<int,int>>maybe[N];
vector<int>ac[N];
int tree[N];
int gtree(int x) { if (x == tree[x]) return x; return tree[x] = gtree(tree[x]); }
int cc[N];
int gcc(int x) { if (x == cc[x]) return x; return cc[x] = gcc(cc[x]); }
int par[N];
void add_edge(int x, int y) {
cerr << "\t" << x << " -> " << y << " edge\n";
tree[x] = y;
par[x] = y;
}
void unite(int x, int y) {
x = gcc(x), y = gcc(y);
if (x == y) return;
if (keys[x].size() + maybe[x].size() + ac[x].size() >
keys[y].size() + maybe[y].size() + ac[y].size()) swap(x, y);
cc[x] = y;
for (auto u : ac[x]) ac[y].emplace_back(u);
ac[x].clear();
for (auto u : keys[x]) {
auto it = maybe[y].lower_bound({u, -1});
while (it != maybe[y].end() && it->first == u) {
ac[y].emplace_back(it->second);
++it;
}
keys[y].insert(u);
}
keys[x].clear();
for (auto it : maybe[x]) {
if (keys[y].count(it.first)) ac[y].emplace_back(it.second);
else maybe[y].insert(it);
}
maybe[x].clear();
}
void collapse(int x, int y) {
cerr << "\t" << x << " -> " << y << " collapse\n";
while (x != y) {
unite(x, y);
y = par[y];
}
int a = gtree(gcc(x));
int b = gcc(x);
tree[b] = b;
tree[a] = b;
cerr << "\ttree " << a << " -> " << b << endl;
}
void push(int v) {
v = gcc(v);
v = gtree(v);
while (ac[v].size()) {
int t = ac[v].back(); ac[v].pop_back();
t = gcc(t);
int tv = gtree(v);
int tt = gtree(t);
if (tv != tt) {
add_edge(v, tt);
push(t);
return;
}
// cycle
collapse(v, t);
v = gcc(v);
v = gtree(v);
push(v);
return;
}
}
vi norm(int n, vi a) {
vi r(n);
for (int i : a) r[i] = 1;
return r;
}
vi find_reachable(vi r, vi u, vi v, vi c) {
int n = r.size();
int m = u.size();
vi ans;
for (int i = 0 ; i < n ; ++ i) {
tree[i] = cc[i] = par[i] = i;
}
for (int i = 0 ; i < m ; ++ i) {
maybe[u[i]].insert({c[i], v[i]});
maybe[v[i]].insert({c[i], u[i]});
}
for (int i = 0 ; i < n ; ++ i) {
keys[i].insert(r[i]);
auto it = maybe[i].lower_bound({r[i], -1});
while (it != maybe[i].end() && it->first == r[i]) ac[i].emplace_back(it->second), it++;
if (ac[i].empty()) ans.emplace_back(i);
}
if (ans.size()) return norm(n, ans);
for (int i = 0 ; i < n ; ++ i) {
push(i);
}
for (int i = 0 ; i < n ; ++ i) {
cerr << gcc(i) << " ";
}
cerr << endl;
vi cnt(n);
for (int i = 0 ; i < n ; ++ i) {
int x = gcc(i);
if (x == gtree(x)) cnt[x]++;
else cnt[x] = N;
}
int mn = N;
for (int i = 0 ; i < n ; ++ i) {
int x = gcc(i);
mn = min(mn, cnt[x]);
}
for (int i = 0 ; i < n ; ++ i) {
cerr << gtree(gcc(i)) << " ";
}
cerr << endl;
for (int i = 0 ; i < n ; ++ i) {
cerr << cnt[i] << " ";
}
cerr << endl;
for (int i = 0 ; i < n ; ++ i) {
int x = gcc(i);
if (cnt[x] == mn) ans.emplace_back(i);
}
return norm(n, ans);
}
