#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using pii=pair<int,int>;
const int lim=3e5+100;
int n,m;
pii edges[lim];
int cnt[lim];
int parent[lim],sz[lim];
unordered_set<int>havekeys[lim];
unordered_map<int,vector<int>>could[lim];
queue<int>q;
bool disabled[lim];
int find(int i){
if(parent[i]==i)return i;
return parent[i]=find(parent[i]);
}
void unite(int i,int j){
i=find(i),j=find(j);
if(i^j){
if(sz[i]<sz[j])swap(i,j);
parent[j]=i;
sz[i]+=sz[j];
vector<int>todel;
if(havekeys[i].size()<could[j].size()){
for(int k:havekeys[i]){
if(could[j].count(k)){
for(int e:could[j][k]){
if((++cnt[e])==2){
q.push(e);
}
}
todel.pb(k);
}
}
}else{
for(auto&[k,v]:could[j]){
if(havekeys[i].count(k)){
for(int e:v){
if((++cnt[e])==2){
q.push(e);
}
}
todel.pb(k);
}
}
}
if(havekeys[j].size()<could[i].size()){
for(int k:havekeys[j]){
if(could[i].count(k)){
for(int e:could[i][k]){
if((++cnt[e])==2){
q.push(e);
}
}
todel.pb(k);
}
}
}else{
for(auto&[k,v]:could[i]){
if(havekeys[j].count(k)){
for(int e:v){
if((++cnt[e])==2){
q.push(e);
}
}
todel.pb(k);
}
}
}
for(int i:todel){
could[i].erase(i);
could[j].erase(i);
}
if(havekeys[i].size()<havekeys[j].size())swap(havekeys[j],havekeys[i]);
for(int k:havekeys[j]){
havekeys[i].insert(k);
}
havekeys[j].clear();
if(could[i].size()<could[j].size())swap(could[j],could[i]);
for(auto&[k,v]:could[j]){
if(could[i].count(k)&&could[i][k].size()<v.size())swap(could[i][k],v);
for(int e:v){
could[i][k].pb(e);
}
}
}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n=r.size(),m=u.size();
for(int i=0;i<n;i++){
parent[i]=i;
sz[i]=1;
havekeys[i].insert(r[i]);
}
for(int i=0;i<m;i++){
edges[i]={u[i],v[i]};
could[u[i]][c[i]].pb(i);
if(r[u[i]]==c[i])cnt[i]++;
could[v[i]][c[i]].pb(i);
if(r[v[i]]==c[i])cnt[i]++;
if(cnt[i]==2)q.push(i);
}
while(q.size()){
int i=q.front();
q.pop();
unite(u[i],v[i]);
}
for(int i=0;i<m;i++){
if(cnt[i]==1){
//cerr<<"edge "<<u[i]<<" "<<v[i]<<"\n";
u[i]=find(u[i]),v[i]=find(v[i]);
/*
cerr<<"keys of "<<u[i]<<": ";
for(int i:havekeys[u[i]]){
cerr<<i<<" ";
}cerr<<"\n";
cerr<<"keys of "<<v[i]<<": ";
for(int i:havekeys[v[i]]){
cerr<<i<<" ";
}cerr<<"\n";
*/
if(havekeys[u[i]].count(c[i])){
disabled[u[i]]=1;
}else if(havekeys[v[i]].count(c[i])){
disabled[v[i]]=1;
}else{
assert(0);
}
}
}
int res=INT_MAX;
vector<int>ans;
for(int i=0;i<n;i++){
int j=find(i);
/*
cerr<<i<<" is in "<<j<<"\n";
cerr<<j<<" is ";
if(disabled[j])cerr<<"disabled\n";
else cerr<<"not disabled\n";
*/
if(!disabled[j]&&sz[j]<res){
res=sz[j];
ans.clear();
}
if(!disabled[j]&&res==sz[j]){
ans.pb(i);
}
}
vector<int>finalans(n,0);
for(int i:ans){
finalans[i]=1;
}
return finalans;
}
