#include "keys.h"
#include <cassert>
#include <vector>
#include <cstdio>
#include <iostream>
#include <queue>
#include <map>
#include <unordered_map>
using namespace std;
int ke[300005];
int sef[300005];
int x[300005];
int y[300005];
int tip[300005];
int fre[300005];
int sz[300005];
int comp[300005];
int find(int a)
{
if(a==sef[a])
{
return a;
}
return sef[a]=find(sef[a]);
}
int findg(int a)
{
if(a==comp[a])
{
return a;
}
return comp[a]=findg(comp[a]);
}
int currmuchie[300005];
map<int,int>keye[300005];
map<int,vector<int>>much[300005];
vector<int>potedges[300005];
void merge(int a,int b)
{
a=find(a);
b=find(b);
if(sz[b]>sz[a])
{
swap(a,b);
}
for(auto x:potedges[b])
{
potedges[a].push_back(x);
}
potedges[b].clear();
for(auto currke:keye[b])
{
if(keye[a].count(currke.first)==0)
{
keye[a][currke.first]=1;
for(auto it:much[a][currke.first])
{
potedges[a].push_back(it);
}
much[a][currke.first].clear();
}
}
for(auto curmuchval:much[b])
{
if(keye[a].count(curmuchval.first))
{
for(auto it:curmuchval.second)
potedges[a].push_back(it);
}
else
{
for(auto it:curmuchval.second)
much[a][curmuchval.first].push_back(it);
}
}
sef[b]=a;
sz[a]=sz[a]+sz[b];
}
queue<pair<int,int>>merges;
void addedge(int nod,int vecin,int id)
{
if(keye[nod].count(id))
{
potedges[nod].push_back(vecin);
}
else
{
much[nod][id].push_back(vecin);
}
}
void reaclcedge(int nod)
{
nod=find(nod);
currmuchie[nod]=-1;
while(potedges[nod].size())
{
int candid=potedges[nod].back();
potedges[nod].pop_back();
if(find(candid)!=nod)
{
currmuchie[nod]=find(candid);
merges.push({nod,find(candid)});
break;
}
}
//cout<<"newedge "<<nod<<" "<<currmuchie[nod]<<'\n';
}
int dim[300005];
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n=r.size();
int m=u.size();
for(int i=1;i<=n;i++)
{
sef[i]=i;
sz[i]=1;
comp[i]=i;
keye[i][r[i-1]]=1;
}
for(int i=0;i<m;i++)
{
addedge(u[i]+1,v[i]+1,c[i]);
addedge(v[i]+1,u[i]+1,c[i]);
}
for(int i=1;i<=n;i++)
{
reaclcedge(i);
}
while(merges.size())
{
auto curr=merges.front();
merges.pop();
if(findg(curr.first)==findg(curr.second))
{
if(find(curr.first)!=find(curr.second))
{
merge(find(curr.first),find(curr.second));
//cout<<"merge "<<find(curr.first)<<" "<<find(curr.second)<<'\n';
reaclcedge(find(curr.first));
}
}
else
{
comp[findg(curr.second)]=findg(curr.first);
}
}
int minim=n+1;
for(int i=1;i<=n;i++)
{
int sf=find(i);
if(currmuchie[sf]==-1)
{
dim[i]=sz[sf];
minim=min(minim,dim[i]);
}
else
{
dim[i]=n+1;
}
}
vector<int>ans;
for(int i=1;i<=n;i++)
{
if(dim[i]==minim)
{
ans.push_back(1);
}
else
{
ans.push_back(0);
}
}
return ans;
}
