#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
const ll MAXN = 3e5+100;
set <ll> out[MAXN];
set <pll> pot[MAXN];
set <ll> keys[MAXN];
set <ll> all[MAXN];
ll in[MAXN];
ll n;
ll dsu[MAXN];
ll f(ll x){
if (dsu[x] < 0)return x;
return (dsu[x] = f(dsu[x]));
}
ll join(ll x,ll y){
if (dsu[x] > dsu[y])swap(x,y);
dsu[x] += dsu[y];
dsu[y] = x;
for (auto z:all[y])out[x].erase(z);
for (auto z:out[y]){
if (all[x].find(z) == all[x].end())out[x].insert(z);
}
for (auto z:keys[y]){
for (auto it = pot[x].lower_bound(MP(z,-1));it != pot[x].end() && (*it).fi == z;it = pot[x].erase(it)){
ll u = (*it).se;
if (all[x].find(u) == all[x].end() && all[y].find(u) == all[y].end())out[x].insert(u);
}
}
for (auto z:pot[y]){
if (keys[x].find(z.fi) != keys[x].end()){
ll u = z.se;
if (all[x].find(u) == all[x].end() && all[y].find(u) == all[y].end())out[x].insert(u);
}
else{
pot[x].insert(z);
}
}
for (auto z:keys[y])keys[x].insert(z);
for (auto z:all[y])all[x].insert(z);
// for (auto z:out[x])assert(all[x].find(z) == all[x].end());
// for (auto z:pot[x])assert(keys[x].find(z.fi)==keys[x].end());
return x;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
n = sz(r);
std::vector<int> ans(r.size());
for (ll i = 0;i < n;i ++){
dsu[i] = -1;
keys[i] = {r[i]};
all[i] = {i};
}
ll m = sz(u);
for (ll i = 0;i < m;i ++){
pot[u[i]].insert(MP(c[i],v[i]));
pot[v[i]].insert(MP(c[i],u[i]));
}
for (ll i = 0;i < n;i ++){
for (auto it = pot[i].begin();it != pot[i].end();){
if ((*it).fi == r[i]){
out[i].insert((*it).se);
it = pot[i].erase(it);
}
else{
it++;
}
}
}
for (ll i = 0;i < n;i ++){
if (!in[i]){
vector <ll> cur;
cur.push_back(i);
in[i] = 1;
while (true){
ll u = cur.back();
// cout<<i<<' '<<u<<endl;
if (out[u].empty())break;
ll v = f(*out[u].begin());
if (in[v]==0){
in[v]=1;
cur.push_back(v);
}
else{
if (in[v]==2){
break;
}
else{
cur.pop_back();
ll last = u;
while (cur.back() != v){
last = join(last,cur.back());
cur.pop_back();
}
last = join(last,cur.back());
cur.pop_back();
cur.push_back(last);
}
}
}
for (auto x:cur)in[x] = 2;
}
}
ll res = n+1;
for (ll i = 0;i < n;i ++){
if (dsu[i]<0 && out[i].empty())res = min(res,-dsu[i]);
}
for (ll i = 0;i < n;i ++){
if (out[f(i)].empty() && -dsu[f(i)] == res)ans[i] = 1;
}
return ans;
}
