#include "keys.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
mt19937 rnd(20041015);
#define fir first
#define sec second
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
namespace wasa855
{
#define N 300005
int fa[N],n;
set<int> keys[N],G[N];
set<pii> H[N];
void att(int u,int v,int col)
{
if(u==v) return ;
if(keys[u].find(col)!=keys[u].end()) G[u].insert(v);
else H[u].emplace(col,v);
}
int find(int u) {return fa[u]==u?u:fa[u]=find(fa[u]);}
void merge(int u,int v)
{
u=find(u),v=find(v);
if(u==v) return ;
// printf("merge %d %d\n",u,v);
fa[v]=u;
// if(keys[u].size()<keys[v].size()) swap(keys[u],keys[v]);
// if(G[u].size()<G[v].size()) swap(G[u],G[v]);
// if(H[u].size()<H[v].size()) swap(H[u],H[v]);
if(keys[u].size()+G[u].size()+H[u].size()<keys[v].size()+G[v].size()+H[v].size()) swap(keys[u],keys[v]),swap(G[u],G[v]),swap(H[u],H[v]);
for(int i:G[v]) G[u].insert(i);
for(int i:keys[v])
{
auto pos=H[u].lower_bound({i,0});
while(pos!=H[u].end()&&pos->fir==i)
{
G[u].insert(pos->sec);
auto nxt=pos; pos++;
H[u].erase(nxt);
}
keys[u].insert(i);
}
for(auto [c,v]:H[v]) att(u,find(v),c);
// printf("out\n");
}
int vis[N],st[N],tp;
void popfront(int u)
{
// printf("^ in %d\n",u);
while(!G[u].empty())
{
int val=*G[u].begin();
if(val!=find(val)&&find(val)!=u) G[u].insert(find(val)),G[u].erase(val);
else if(find(val)==u) G[u].erase(val);
else break;
}
// printf("out\n");
}
void work(int u)
{
st[++tp]=u,vis[u]=1;
while(tp)
{
popfront(u);
if(G[u].empty())
{
vis[st[tp--]]=2;
u=st[tp];
continue;
}
int v=*G[u].begin();
G[u].erase(v);
// printf("^ %d %d\n",u,v);
if(vis[v]==2) continue;
if(vis[v]==1)
{
while(st[tp]!=v) merge(v,st[tp]),vis[st[tp--]]=0;
u=find(st[tp]);
}
if(vis[v]==0)
{
st[++tp]=v,vis[v]=1;
u=v;
}
}
}
vector<int> Main(vector<int> a,vector<int> u,vector<int> v,vector<int> c)
{
n=a.size();
for(int i=0;i<n;i++) fa[i]=i,keys[i].insert(a[i]);
for(int i=0;i<(int)u.size();i++) att(u[i],v[i],c[i]),att(v[i],u[i],c[i]);
for(int i=0;i<n;i++) if(!vis[i]) work(i);
// for(int i=0;i<n;i++) printf("%d%c",find(i)," \n"[i==n-1]);
vector<int> siz(n),dgr(n);
for(int i=0;i<n;i++) siz[find(i)]++;
for(int i=0;i<(int)u.size();i++)
{
u[i]=find(u[i]),v[i]=find(v[i]);
if(u[i]==v[i]) continue;
if(keys[u[i]].find(c[i])!=keys[u[i]].end()) dgr[u[i]]++;
if(keys[v[i]].find(c[i])!=keys[v[i]].end()) dgr[v[i]]++;
}
// print(dgr);
int mn=inf;
for(int i=0;i<n;i++) if(find(i)==i&&!dgr[i]) mn=min(mn,siz[i]);
vector<int> ans(n);
for(int i=0;i<n;i++)
{
int u=find(i);
if(!dgr[u]&&siz[u]==mn) ans[i]=1;
}
return ans;
}
};
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
return wasa855::Main(r,u,v,c);
}
