#include<bits/stdc++.h>
#include "keys.h"
using namespace std;
typedef long long ll;
struct E{
int fr,to,val;
};
int n,m,bel[300005],low[300005],dfn[300005],ins[300005],sign,st[300005],top,SCC;
int a[300005],oud[300005],fa[300005],ind[300005],vst[300005],clx[300005];
vector<int> g[300005];
vector<E> G[300005];
bool T;
bool operator <(E x,E y){return x.val!=y.val?x.val<y.val:x.to!=y.to?x.to<y.to:x.fr<y.fr;}
void dfs(int x){
st[++top]=x,low[x]=dfn[x]=++sign,ins[x]=1;
for(int y:g[x]){
if(!dfn[y])dfs(y),low[x]=min(low[x],low[y]);
else if(ins[y])low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
int tmp=0;
SCC++;
while(tmp!=x)bel[tmp=st[top--]]=SCC,ins[tmp]=0,ind[SCC]++;
}
}
vector<E> edge[300005];
bool key[300005];
int clk[300005],cle[300005],iscle[300005];
queue<int> q;
int gf(int x){
return fa[x]==x?x:fa[x]=gf(fa[x]);
}
struct W{
int x,y;
}t[10000005];
int cnt=0;
void Inskey(int x){
if(key[x])return ;
key[x]=1,clk[++clk[0]]=x;
//cout<<"Ins:"<<x<<'\n';
while(edge[x].size()&&!T){
E it=edge[x].back();
if(!vst[it.to]){
q.push(it.to);
if(gf(it.fr)!=gf(it.to))T=1;
else vst[it.to]=1,clx[++clx[0]]=it.to;
}
t[++cnt]={it.fr,it.to};
edge[x].pop_back();
}
}
void InsEdge(E x){
//cout<<x.val<<' '<<key.count(x.val)<<'\n';
if(key[x.val]){
if(!vst[x.to]){
q.push(x.to);
if(gf(x.fr)!=gf(x.to))T=1;
else vst[x.to]=1,clx[++clx[0]]=x.to;
}
t[++cnt]={x.fr,x.to};
}
else {
if(!iscle[x.val])iscle[x.val]=1,cle[++cle[0]]=x.val;
edge[x.val].push_back(x);
}
}
void bfs(int x){
//cout<<"AA:"<<key.size()<<' '<<key.count(0)<<'\n';
q.push(x),vst[x]=1,clx[++clx[0]]=x;//,cout<<i<<'\n';
while(!q.empty()){
int x=q.front();
q.pop(),Inskey(a[x]);
if(T){
while(!q.empty())q.pop();
break;
}
for(E i:G[x]){
InsEdge(i);
if(T)break;
}
if(T){
while(!q.empty())q.pop();
}
}
//puts("PP");
while(clk[0])key[clk[clk[0]--]]=0;
while(clx[0])vst[clx[clx[0]--]]=0;
while(cle[0])iscle[cle[cle[0]]]=0,edge[cle[cle[0]--]].clear();
}
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=1;i<=n;i++)a[i]=R[i-1],fa[i]=i;
for(int i=1,x,y,z;i<=m;i++){
x=U[i-1],y=V[i-1],z=C[i-1];
x++,y++;
G[x].push_back({x,y,z}),G[y].push_back({y,x,z});
}
int nfl=0;
while(1){
bool fl=0;
for(int i=1;i<=n;i++)if(gf(i)==i)T=0,bfs(i),fl|=T;
for(int i=1;i<=cnt;i++)fa[gf(t[i].x)]=gf(t[i].y),g[t[i].x].push_back(t[i].y);
cnt=0;
if(!fl){
nfl++;
if(nfl==2)break;
}
}
for(int i=1;i<=n;i++)
sort(g[i].begin(),g[i].end()),g[i].resize(unique(g[i].begin(),g[i].end())-g[i].begin());
for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
for(int i=1;i<=n;i++)for(int j:g[i])if(bel[i]!=bel[j])oud[bel[i]]++;
int mn=1e9;
for(int i=1;i<=SCC;i++)if(!oud[i])mn=min(mn,ind[i]);
cerr<<mn<<'\n';
vector<int> ans(n);
for(int i=1;i<=n;i++)if(!oud[bel[i]]&&ind[bel[i]]==mn)ans[i-1]=1;
return ans;
}
