#include <bits/stdc++.h>
using namespace std;
const int nax=2e5+5;
#define pb push_back
#define fi first
#define se second
int parent[nax];
vector<int> adj[nax];
vector<int> rev_adj[nax];
set<int> colors[nax];
int vis[nax];
int sz[nax];
vector<int> order;
void push(int x){
vis[x]=true;
for(auto u:adj[x]){
if(vis[u]) continue;
push(u);
}
order.pb(x);
}
void pull(int x,vector<int>& cur){
vis[x]=true;
for(auto u:rev_adj[x]){
if(vis[u]) continue;
pull(u,cur);
}
cur.pb(x);
}
int dfs(int x,int p){
for(auto u:adj[x]){
if(u==p) continue;
sz[x]+=dfs(u,x);
}
return sz[x];
}
int find(int x){
if(x==parent[x]) return x;
return parent[x]=find(parent[x]);
}
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 = 0; i < n; ++i) colors[i].insert(r[i]);
for (int i = 0; i < n; ++i) parent[i]=i;
for (int i = 0; i < n; ++i) sz[i]=1;
for (int i = 0; i < m; ++i)
{
if(c[i]==r[u[i]]){
rev_adj[v[i]].pb(u[i]);
adj[u[i]].pb(v[i]);
}
if(c[i]==r[v[i]]){
rev_adj[u[i]].pb(v[i]);
adj[v[i]].pb(u[i]);
}
}
for (int i = 0; i < n; ++i)
{
if(!vis[i]) push(i);
}
reverse(order.begin(),order.end());
memset(vis,0,sizeof vis);
for(auto u:order){
if(!vis[u]){
vector<int> component;
pull(u,component);
sort(component.begin(),component.end());
int p=component[0];
for(auto i:component){
parent[i]=p;
if(i==p) continue;
sz[p]++;
colors[p].insert(r[i]);
}
}
}
for (int i = 0; i < n; ++i)
{
adj[i].clear();
rev_adj[i].clear();
}
for (int i = 0; i < m; ++i)
{
if(parent[u[i]]==parent[v[i]]) continue;
int x=parent[u[i]];
int y=parent[v[i]];
if(colors[x].count(c[i])){
rev_adj[y].pb(x);
adj[x].pb(y);
}
if(colors[y].count(c[i])){
rev_adj[x].pb(y);
adj[y].pb(x);
}
}
for (int i = 0; i < n; ++i)
{
vector<int> cur;
sort(adj[i].begin(),adj[i].end());
for (int j = 0; j < (int)adj[i].size(); ++j)
{
if(adj[i][j]!=adj[i][j+1]||j==(int)adj[i].size()-1)
cur.pb(adj[i][j]);
}
adj[i]=cur;
}
for (int i = 0; i < n; ++i)
{
vector<int> cur;
sort(rev_adj[i].begin(),rev_adj[i].end());
for (int j = 0; j < (int)rev_adj[i].size(); ++j)
{
if(rev_adj[i][j]!=rev_adj[i][j+1]||j==(int)rev_adj[i].size()-1)
cur.pb(rev_adj[i][j]);
}
rev_adj[i]=cur;
}
memset(vis,0,sizeof vis);
order.clear();
for (int i = 0; i < n; ++i)
{
if(!vis[parent[i]]) push(parent[i]);
}
reverse(order.begin(),order.end());
memset(vis,0,sizeof vis);
for(auto u:order){
if(!vis[u]){
vector<int> component;
pull(u,component);
sort(component.begin(),component.end());
int p=component[0];
for(auto i:component){
if(i==p) continue;
parent[i]=p;
sz[p]+=sz[i];
for(auto v:colors[i]) colors[i].insert(v);
}
}
}
for (int i = 0; i < n; ++i)
{
adj[i].clear();
rev_adj[i].clear();
}
for (int i = 0; i < m; ++i)
{
if(find(u[i])==find(v[i])) continue;
int x=parent[u[i]];
int y=parent[v[i]];
if(colors[x].count(c[i])){
adj[x].pb(y);
}
if(colors[y].count(c[i])){
adj[y].pb(x);
}
}
for (int i = 0; i < n; ++i)
{
vector<int> cur;
sort(adj[i].begin(),adj[i].end());
for (int j = 0; j < (int)adj[i].size(); ++j)
{
if(adj[i][j]!=adj[i][j+1]||j==(int)adj[i].size()-1)
cur.pb(adj[i][j]);
}
adj[i]=cur;
}
int mn=n;
memset(vis,0,sizeof vis);
for (int i = 0; i < n; ++i)
{
if(vis[find(i)]) continue;
dfs(find(i),-1);
mn=min(mn,sz[find(i)]);
}
vector<int> ans(n);
for (int i = 0; i < n; ++i)
{
ans[i]=(sz[find(i)]==mn ? 1 : 0);
}
return ans;
}
