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