#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef set<int> si;
vi dfn, mi;
vi stk;
vb ist, vis;
int cdfn = 1;
vvi gp;
vi gi;
void tarjan(int c, vvi& adj) {
assert(!vis[c]);
mi[c] = dfn[c] = cdfn++;
stk.push_back(c);
assert(!ist[c]); ist[c] = true;
vis[c] = true;
for(int i : adj[c]) {
if(!vis[i]) {
tarjan(i, adj);
} else if(ist[i]) {
mi[c] = min(mi[c], dfn[i]);
}
}
if(mi[c] == dfn[c]){
gp.emplace_back();
int cur;
do{
cur = stk.back();
gi[cur] = (int) gp.size() - 1;
stk.pop_back(); ist[cur] = false;
gp.back().push_back(cur);
} while(cur != c);
}
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = r.size(), m = u.size();
int k = 1;
forR(i, m) k = max(k, c[i] + 1);
forR(i, n) k = max(k, r[i] + 1);
int N = n * k;
vvi adj(N);
// room i, key j -> i * k + j
forR(i, n) forR(j, k) if(j != r[i]) adj[i * k + j].push_back(i * k + r[i]);
forR(i, m) {
adj[u[i] * k + c[i]].push_back(v[i] * k + c[i]);
adj[v[i] * k + c[i]].push_back(u[i] * k + c[i]);
}
dfn.resize(N); mi.resize(N); ist.resize(N); vis.resize(N); gi.resize(N);
forR(i, N) if(!vis[i]){
assert(stk.empty());
tarjan(i, adj);
}
forR(i, N) assert(vis[i]);
// cerr << gp.size() << '\n';
// forR(i, N) cerr << gi[i] << ' ';
// cerr << '\n';
vi gpt(gp.size());
forR(i, n) gpt[gi[i * k + r[i]]] += 1;
vector<si> gAdj(gp.size());
forR(i, N) for(int j : adj[i]) if(gi[j] != gi[i]) gAdj[gi[i]].insert(gi[j]);
forR(i, gp.size()) {
for(int j : gAdj[i]) gpt[i] += gpt[j];
}
vi cnt(n);
forR(i, n) cnt[i] = gpt[gi[i * k + r[i]]];
int mi = cnt[0];
forR(i, n) mi = min(mi, cnt[i]);
vi ans(n);
forR(i, n) ans[i] = cnt[i] == mi ? 1 : 0;
return ans;
}
