#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;
int n,m,cnt;
bool used[MAXN],reach[MAXN],dali;
int ans[MAXN],mins;
vector<int> sol,perm,edges;
vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c){
n=int(r.size()); m=int(u.size());
mins=n;
for(int i=0;i<n;i++)perm.push_back(i);
random_shuffle(perm.begin(),perm.end());
for(int i:perm){
for(int f=0;f<n;f++){
used[f]=false; reach[f]=false;
}
edges.clear();
for(int f=0;f<m;f++)edges.push_back(f);
used[r[i]]=true; reach[i]=true;
dali=true; cnt=1;
while(dali){
dali=false;
for(int k=0;k<edges.size();k++){
if(reach[u[edges[k]]] and !reach[v[edges[k]]] and used[c[edges[k]]]){
reach[v[edges[k]]]=true; used[r[v[edges[k]]]]=true;
dali=true; cnt++;
swap(edges[k],edges[edges.size()-1]); edges.pop_back();
}
if(!reach[u[edges[k]]] and reach[v[edges[k]]] and used[c[edges[k]]]){
reach[u[edges[k]]]=true; used[r[u[edges[k]]]]=true;
dali=true; cnt++;
swap(edges[k],edges[edges.size()-1]); edges.pop_back();
}
}
if(cnt>mins)break;
}
ans[i]=cnt;
mins=min(mins,cnt);
}
for(int i=0;i<n;i++){
if(ans[i]==mins){
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});
}
*/
