#include <vector>
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define INF 1000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#define ll long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#ifdef wiwihorz
#define print(a...) cerr << "Line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() {cerr << endl;}
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
int ii;
vector<vector<pii>> mp;
vector<int> R, instack;
set<int> avail;
namespace dsu {
int n;
vector<int> sz, par;
vector<set<int>> col;
vector<set<pii>> good, bad;
void init_(int _n) {
n = _n;
sz.assign(n + 1, 1);
par.assign(n + 1, 0);
col.assign(n + 1, set<int>());
good.assign(n + 1, set<pii>());
bad.assign(n + 1, set<pii>());
rep(i, 0, n - 1) {
par[i] = i;
col[i].insert(R[i]);
for(auto j : mp[i]) {
if(j.first == R[i]) good[i].insert(j);
else bad[i].insert(j);
}
}
}
int find_par(int a) {
while(a != par[a]) a = par[a];
return par[a];
}
bool same(int a, int b) {
return find_par(a) == find_par(b);
}
void unite(int a, int b) {
int aa = find_par(a);
int bb = find_par(b);
if(aa == bb) return;
if(sz[aa] < sz[bb]) swap(aa, bb);
sz[aa] += sz[bb], par[bb] = aa;
if(good[aa].size() < good[bb].size()) {
for(auto i : good[aa]) good[bb].insert(i);
good[aa].swap(good[bb]);
}
else for(auto i : good[bb]) good[aa].insert(i);
good[bb].clear();
for(auto i : col[bb]) {
col[aa].insert(i);
auto it = bad[aa].lower_bound(pii(i, -INF));
while(it != bad[aa].end() && it->first == i ) {
good[aa].insert({it->first, it->second});
auto temp = it; it = next(it);
bad[aa].erase(temp);
}
}
// wrong
col[bb].clear();
for(auto i : bad[bb]) {
if(col[aa].find(i.first) != col[aa].end()) {
good[aa].insert(i);
}
else bad[aa].insert(i);
}
bad[bb].clear();
}
};
int get(int x) { return dsu::find_par(x); }
void operate(int x) {
stack<int> st;
st.push(x);
instack[x] = ii;
bool ok = 1;
while(dsu::good[get(st.top())].size()) {
int p = get(st.top());
pii cur = *dsu::good[p].begin();
dsu::good[p].erase(dsu::good[p].find(cur));
if(dsu::same(cur.second, p)) continue;
cur.second = get(cur.second);
if(instack[cur.second] && instack[cur.second] != ii) {
ok = 0;
break;
}
else if(instack[cur.second]) {
while(get(st.top()) != get(cur.second)) {
int k = st.top(); st.pop();
dsu::unite(k, cur.second);
}
}
else {
instack[cur.second] = ii;
st.push(cur.second);
}
}
if(ok) avail.insert(get(st.top()));
return;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
vector<int> ans(r.size(), 0);
int n = r.size();
R = r, ii = 0;
mp.assign(n, vector<pii>());
instack.assign(n, 0);
rep(i, 0, signed(u.size()) - 1) {
mp[u[i]].push_back({c[i], v[i]});
mp[v[i]].push_back({c[i], u[i]});
}
dsu::init_(n);
rep(i, 0, n - 1) {
if(!instack[i]) ii ++, operate(i);
}
int mn = INF;
rep(i, 0, n - 1) if(avail.find(get(i)) != avail.end()) {
mn = min(mn, dsu::sz[get(i)]);
}
rep(i, 0, n - 1) if(avail.find(get(i)) != avail.end()) {
if(dsu::sz[get(i)] == mn) ans[i] = 1;
}
return ans;
}
