#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include "keys.h"
using namespace std;
const int MAX_N=3e5+5;
vector<pair<int,int>>g[MAX_N];
vector<int>wait[MAX_N];
vector<int>takennodes;
vector<int>waitclear;
bool taken[MAX_N];
bool keys[MAX_N];
queue<int>q;
int N;
vector<int>key;
int parent[MAX_N];
int sz[MAX_N];
int Find(int u)
{
if(parent[u]==u)return u;
return parent[u]=Find(parent[u]);
}
void Merge(int u,int v)
{
int urt=Find(u);
int vrt=Find(v);
if(urt==vrt)return;
sz[vrt]+=sz[urt];
parent[urt]=vrt;
}
bool calc=0;
vector<pair<int,int>>pairs;
int bfs(int s)
{
while(q.size())q.pop();
q.push(s);
while(q.size())
{
int u=q.front();
q.pop();
if(taken[u])continue;
taken[u]=1;
takennodes.push_back(u);
if(Find(u)!=Find(s))
{
if(!calc)
{
pairs.push_back({s,u});
break;
}
}
keys[key[u]]=1;
for(int v:wait[key[u]])q.push(v);
wait[key[u]].clear();
for(auto [v,c]:g[u])
{
if(keys[c])q.push(v);
else
{
waitclear.push_back(c);
wait[c].push_back(v);
}
}
}
int cnt=takennodes.size();
for(int u:takennodes)
{
keys[key[u]]=0;
taken[u]=0;
}
for(int c:waitclear)
{
wait[c].clear();
}
takennodes.clear();
waitclear.clear();
return cnt;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c)
{
key=r;
N=r.size();
for(int i=0;i<u.size();i++)
{
g[u[i]].push_back({v[i],c[i]});
g[v[i]].push_back({u[i],c[i]});
}
for(int i=0;i<N;i++)
{
parent[i]=i;
sz[i]=1;
}
for(int times=0;times<30;times++)
{
pairs.clear();
for(int i=0;i<N;i++)
{
if(parent[i]!=i)continue;
bfs(i);
}
for(auto [x,y]:pairs)
{
Merge(x,y);
}
}
calc=1;
int mi=1e9;
vector<int>minnodes;
for(int i=0;i<N;i++)
{
if(parent[i]!=i)continue;
int cur=bfs(i);
if(cur<mi)
{
minnodes.clear();
minnodes.push_back(i);
mi=cur;
}
else if(cur==mi)minnodes.push_back(i);
}
vector<int>ans;
ans.resize(N);
for(int u:minnodes)ans[u]=1;
return ans;
}
