#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<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);
}
}
for (ll m: emrg) {
ll x = edg[m].first.first;
ll y = edg[m].first.second;
mrg(x,y);
}
}
vector<int> find_reachable(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;
akey[i].insert(r[i]);
}
vector<pii> adj[N]; //vertex, key type
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]});
adj[v[m]].push_back({u[m],c[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 (pii p0: adj[i]) {
if (r[i]==p0.second) {
fadj[i]=p0; break;
}
}
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++) {
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) {
continue;
}
do {
//mrg(x,fadj[x].first);
x = fadj[x].first;
ocyc[x]=1;
//cout << "find x="<<x<<"\n";
if (mop[x].find(r[x])!=mop[x].end()) {
for (ll m: mop[x][r[x]]) {
ec.push_back(m);
}
}
} while (x!=y);
for (ll z: vnum) {
found[z]=1;
}
}
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;
}
