#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
const ll Nm = 3e5+5;
vector<pair<pii,ll>> edg; //{u,v},c
ll dsuf[Nm];
map<ll,vector<ll>> mop[Nm]; //map: key -> edge vector to open
set<ll> akey[Nm]; //active keys
vector<ll> iedg[Nm];
vector<bool> iact(Nm,0); //initially activated?
vector<ll> nelem(Nm,1); //number of elements in this group
ll getf(ll a) {
if (dsuf[a]==a) {
return a;
}
dsuf[a]=getf(dsuf[a]);
return dsuf[a];
}
void mrg(ll a, ll b) {
ll _a = a; ll _b = b;
a = getf(a); b = getf(b);
if (a==b) {
return;
}
//cout << "implementing merge: "<<_a<<" with "<<_b<<"\n";
if (nelem[a]>nelem[b]) {
swap(a,b);
}
dsuf[a]=b;
nelem[b]+=nelem[a];
//merge numbers
vector<ll> emrg;
for (ll x: akey[a]) {
if (mop[b].find(x)!=mop[b].end()) {
for (ll m: mop[b][x]) {
emrg.push_back(m);
}
}
akey[b].insert(x);
}
for (auto A0: mop[a]) {
ll k0 = A0.first; vector<ll> vedg = A0.second;
if (akey[b].find(k0)!=akey[b].end()) {
for (ll m: vedg) {
emrg.push_back(m);
}
}
for (ll m: vedg) {
mop[b][k0].push_back(m);
}
}
if (!iact[_a]) {
iact[_a]=1;
for (ll m: iedg[_a]) {
emrg.push_back(m);
}
}
if (!iact[_b]) {
iact[_b]=1;
for (ll m: iedg[_b]) {
emrg.push_back(m);
}
}
for (ll m: emrg) {
ll x = edg[m].first.first;
ll y = edg[m].first.second;
mrg(x,y);
}
}
vector<int> find_reachable_fast(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
ll N = r.size(); ll M = u.size();
for (ll i=0;i<N;i++) {
dsuf[i]=i;
mop[i].clear();
akey[i].clear();
iedg[i].clear();
iact[i]=0;
nelem[i]=1;
}
for (ll i=0;i<N;i++) {
akey[i].insert(r[i]);
}
vector<pair<pii,ll>> adj[N]; //{vertex, key type},edge index
edg.clear();
for (ll m=0;m<M;m++) {
edg.push_back({{u[m],v[m]},c[m]});
adj[u[m]].push_back({{v[m],c[m]},m});
adj[v[m]].push_back({{u[m],c[m]},m});
mop[u[m]][c[m]].push_back(m);
mop[v[m]][c[m]].push_back(m);
}
vector<pii> fadj(N,{-1,-1}); //{vertex, key type}
vector<ll> vblk;
for (ll i=0;i<N;i++) {
for (auto A0: adj[i]) {
pii p0 = A0.first;
if (r[i]==p0.second) {
fadj[i]=p0;
iedg[i].push_back(A0.second);
}
}
if (fadj[i].first==-1) {
vblk.push_back(i);
}
}
if (vblk.size()!=0) {
//cout << "early terminate\n";
vector<ll> vans(N,0);
for (ll x: vblk) {
vans[x]=1;
}
return vans;
}
vector<bool> found(N,0); //get all cycles
vector<bool> ocyc(N,0); //on cycle?
vector<ll> ec; //edges that follow from cycle terms
for (ll i=0;i<N;i++) {
ll x = i;
ll y = i;
for (ll t=0;t<=N;t++) {
x = fadj[x].first;
if (x==y) {
ocyc[i]=1;
}
}
}
// for (ll i=0;i<N;i++) {
// if (found[i]) {
// continue;
// }
// //cout << "cycle find at i="<<i<<"\n";
// ll x = i;
// ll y = i;
// bool bbrk = 0;
// vector<ll> vnum; vnum.push_back(i);
// do {
// if (found[x]) {
// bbrk = 1; break;
// }
// x = fadj[x].first;
// vnum.push_back(x);
// y = fadj[fadj[y].first].first;
// } while (x!=y);
// if (bbrk) {
// for (ll z: vnum) {
// found[z]=1;
// }
// continue;
// }
// do {
// //mrg(x,fadj[x].first);
// x = fadj[x].first;
// ocyc[x]=1;
// //cout << "find x="<<x<<"\n";
// } while (x!=y);
// for (ll z: vnum) {
// found[z]=1;
// }
// }
for (ll x=0;x<N;x++) {
if (ocyc[x]==1) {
//cout << "x="<<x<<" on initial cycle\n";
if (mop[x].find(r[x])!=mop[x].end()) {
for (ll m: mop[x][r[x]]) {
ec.push_back(m);
}
}
}
}
for (ll m: ec) {
ll x = edg[m].first.first;
ll y = edg[m].first.second;
mrg(x,y);
}
ll minp = N+1;
vector<ll> vconstr;
for (ll i=0;i<N;i++) {
ll x = getf(i);
//cout << "i="<<i<<", x="<<x<<", nelem[x]="<<nelem[x]<<"\n";
if (nelem[x]==1) {
continue;
}
if (nelem[x]<minp) {
minp = nelem[x]; vconstr.clear();
}
if (nelem[x]==minp) {
vconstr.push_back(i);
}
}
assert(vconstr.size()!=0);
vector<ll> vans(N,0);
for (ll x: vconstr) {
vans[x]=1;
}
return vans;
}
vector<int> find_reachable_slow(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
ll N = r.size(); ll M = u.size();
ll ans[N];
map<ll,vector<ll>> mf;
for (ll i=0;i<N;i++) {
set<ll> s0;
s0.insert(i);
set<ll> s1;
s1.insert(r[i]);
for (ll T=0;T<M;T++) {
for (ll j=0;j<M;j++) {
if (s1.find(c[j])!=s1.end()) {
if (s0.find(u[j])!=s0.end() || s0.find(v[j])!=s0.end()) {
s0.insert(u[j]);
s0.insert(v[j]);
s1.insert(r[u[j]]);
s1.insert(r[v[j]]);
}
}
}
}
ans[i]=s0.size();
mf[ans[i]].push_back(i);
}
vector<ll> vc = (*(mf.begin())).second;
vector<ll> fans(N,0);
for (ll x: vc) {
fans[x]=1;
}
return fans;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
return find_reachable_slow(r,u,v,c);
}
