#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;
int n,m,w[MAXN],dp[MAXN];
vector<int> v[MAXN],r[MAXN],sol;
bool li[MAXN],used[2*MAXN];
int k,comp[MAXN],br[MAXN],mins,out[MAXN];
unordered_set<int> keys[MAXN];
stack<int> st;
void dfs(int x){
li[x]=true;
for(int i=0;i<v[x].size();i++){
if(!li[v[x][i]])dfs(v[x][i]);
}
st.push(x);
}
void scc(int x){
li[x]=true; comp[x]=k;
keys[k].insert(w[x]);
for(int i=0;i<r[x].size();i++){
if(!li[r[x][i]])scc(r[x][i]);
}
}
vector<int> find_reachable(vector<int> R,vector<int> a,vector<int> b,vector<int> c){
n=int(R.size()); m=int(c.size());
for(int i=0;i<n;i++){
w[i]=R[i];
keys[i].insert(w[i]);
comp[i]=i;
}
for(int test=0;test<10;test++){
for(int i=0;i<m;i++){
if(!used[2*i] and keys[comp[a[i]]].find(c[i])!=keys[comp[a[i]]].end()){
v[a[i]].push_back(b[i]);
r[b[i]].push_back(a[i]);
used[2*i]=true;
}
if(!used[2*i+1] and keys[comp[b[i]]].find(c[i])!=keys[comp[b[i]]].end()){
v[b[i]].push_back(a[i]);
r[a[i]].push_back(b[i]);
used[2*i+1]=true;
}
}
for(int i=0;i<n;i++)li[i]=false;
k=0;
for(int i=0;i<n;i++){
if(!li[i])dfs(i);
}
for(int i=0;i<n;i++){
li[i]=false; keys[i].clear();
}
while(!st.empty()){
if(!li[st.top()]){
scc(st.top()); k++;
}
st.pop();
}
}
for(int i=0;i<n;i++)br[comp[i]]++;
for(int i=0;i<m;i++){
if(comp[a[i]]==comp[b[i]])continue;
if(keys[comp[a[i]]].find(c[i])!=keys[comp[a[i]]].end()){
out[comp[a[i]]]++;
}
if(keys[comp[b[i]]].find(c[i])!=keys[comp[b[i]]].end()){
out[comp[b[i]]]++;
}
}
mins=n;
for(int i=0;i<k;i++){
if(out[i]==0){
mins=min(mins,br[i]);
}
}
for(int i=0;i<n;i++){
if(br[comp[i]]==mins and out[comp[i]]==0)sol.push_back(1);
else sol.push_back(0);
}
return sol;
}
/*
int main(){
//find_reachable({0, 1, 1, 2},{0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
find_reachable({0, 1, 1, 2, 2, 1, 2},
{0, 0, 1, 1, 2, 3, 3, 4, 4, 5},
{1, 2, 2, 3, 3, 4, 5, 5, 6, 6},
{0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
}
*/
