#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#include <bits/stdc++.h>
using namespace std;
const int n_max = 301000;
const int k_max = 301000;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
#define rand rd
vector<pair<int,int>> adj[n_max];
bool visited[n_max];
int original_key[n_max];
int has_key[k_max];
vector<int> blocked[k_max];
int n;
int explore(int x, int bound) {
REP(i, n) {
visited[i] = false;
has_key[i] = false;
blocked[i].clear();
}
visited[x] = true;
queue<int> q;
q.push(x);
int ans = 0;
while(!q.empty() && ans < bound) {
const int next = q.front();
q.pop();
ans++;
int new_key = original_key[next];
if(!has_key[new_key]) {
has_key[new_key] = true;
for(int i: blocked[new_key]) {
if(!visited[i]) {
visited[i] = true;
q.push(i);
}
}
}
for(pair<int,int> p: adj[next]) {
if(has_key[p.first]) {
if(!visited[p.second]) {
visited[p.second] = true;
q.push(p.second);
}
} else blocked[p.first].push_back(p.second);
}
}
return ans;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int m = c.size();
n = r.size();
REP(i, n) original_key[i] = r[i];
REP(i, m) {
adj[u[i]].emplace_back(c[i], v[i]);
adj[v[i]].emplace_back(c[i], u[i]);
}
int a[n];
int s = n+1;
vector <int> perm(n);
iota(ALL(perm), 0);
shuffle(ALL(perm), rd);
REP(i, n) {
a[i] = explore(perm[i], s);
s = min(s, a[i]);
}
vector<int> ans(n);
REP(i, n) if(a[i] == s) ans[i] = 1;
return ans;
}
