#include <bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
struct dsu{
int n;
vector<int> par,sz;
dsu(int s)
{
n = s;
par.resize(n);
sz.resize(n,1);
for(int i =0 ; i< n; i++)
par[i] = i;
}
int fnd(int x)
{
if(par[x]==x)return x;
return par[x] = fnd(par[x]);
}
bool unite(int a,int b)
{
a =fnd(a),b = fnd(b);
if(a==b)return true;
if(sz[a]>sz[b])
swap(a,b);
par[a] = b;
sz[b]+=sz[a];
return false;
}
};
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n =r.size();
int m = u.size();
dsu mile(n);
vector<vector<pii>> cols(n);
for(int i = 0; i < m; i++)
cols[c[i]].push_back({u[i],v[i]});
vector<pii> edges;
vector<int> coord;
for(int i = 0; i< n; i++)
coord.push_back(i);
for(int col = 0;col < n; col++)
{
for(pii x : cols[col])
mile.unite(x.ff,x.ss);
for(pii x :cols[col])
{
int a = x.ff;
for(int it = 0;it < 2;it++)
{
edges.push_back({(col+1)*n+mile.fnd(a),a});
if(r[a]==col)
edges.push_back({a,(col+1)*n+mile.fnd(a)});
coord.push_back(a);
coord.push_back((col+1)*n+mile.fnd(a));
a = x.ss;
}
}
for(pii x:cols[col])
mile.par[x.ff]=x.ff,mile.par[x.ss]=x.ss,
mile.sz[x.ff]=1,mile.sz[x.ss]=1;
}
sort(coord.begin(),coord.end());
coord.resize(unique(coord.begin(),coord.end())-coord.begin());
for(pii&x:edges)
x.ff = lower_bound(coord.begin(),coord.end(),x.ff)-coord.begin(),
x.ss=lower_bound(coord.begin(),coord.end(),x.ss)-coord.begin();
//samo k koristit...
int k =coord.size();
vector<vector<int>> graph(k);
for(pii x:edges)
graph[x.ff].push_back(x.ss);
vector<vector<int>> rev(k);
for(pii x:edges)
rev[x.ss].push_back(x.ff);
vector<int> ord;
vector<int> vis(k,0);
function<void(int)> dfs = [&](int cur){
if(vis[cur])return;
vis[cur] = 1;
for(int a:graph[cur])
dfs(a);
ord.push_back(cur);
};
vector<int> scc(k);
for(int i = 0; i< k; i++)
dfs(i);
reverse(ord.begin(),ord.end());
vis.assign(k,0);
function<void(int,int)> rfs = [&](int cur,int r)
{
if(vis[cur])return;
scc[cur] = r;
vis[cur] = 1;
for(int a: rev[cur])
rfs(a,r);
};
for(int x:ord)
rfs(x,x);
vector<int> sz(k,0);
vector<int> moze(k,1);
for(pii x:edges)
{
if(scc[x.ff]!=scc[x.ss])
moze[scc[x.ff]] = 0;
}
vector<int> ans(n,0);
for(int i = 0; i< n; i++)
sz[scc[i]]++;
int mini = n+1;
for(int i =0 ; i < n; i++)
if(moze[scc[i]])
mini = min(mini,sz[scc[i]]);
for(int i = 0; i < n; i++)
if(moze[scc[i]] && sz[scc[i]]==mini)
ans[i] = 1;
if(mini==n+1)
ans.assign(n,1);
return ans;
}
