#include <bits/stdc++.h>
using namespace std;
const int maxN = 3e5 + 20;
set<int> S;
struct comp {
set<int> rooms;
map<int, set<pair<int, int>>> edges;
set<int> cands, keys;
int edge_cnt = 0;
int id = -1;
int par = -1;
void add_cand(int k) {
if (par == -1 && cands.empty()) {
S.insert(id);
}
cands.insert(k);
}
void add_key(int k) {
keys.insert(k);
if (edges.find(k) != edges.end()) {
add_cand(k);
}
}
void add_edge(int u, int v, int k) {
if (u > v) {
swap(u, v);
}
if (edges[k].find(make_pair(u, v)) == edges[k].end()) {
edges[k].emplace(u, v);
edge_cnt++;
}
if (keys.find(k) != keys.end()) {
add_cand(k);
}
}
};
struct DSU {
int par[maxN];
int depth[maxN];
void init(int N) {
for (int i = 0; i < N; i++) {
par[i] = -1;
depth[i] = 0;
}
}
int root(int u) {
return (par[u] == -1 ? u : (par[u] = root(par[u])));
}
void join(int u, int v) {
u = root(u);
v = root(v);
if (depth[u] > depth[v]) {
swap(u, v);
}
par[u] = v;
if (depth[u] == depth[v]) {
depth[v]++;
}
}
} D;
comp comps[maxN];
int comp_id[maxN];
int cnt;
void merge(int X, int Y) {
if (comps[X].rooms.size() > comps[Y].rooms.size()) {
swap(X, Y);
}
comps[Y].par = -1;
assert(comps[Y].id == Y);
assert(comps[X].id == X);
for (auto u: comps[X].rooms) {
comp_id[u] = Y;
comps[Y].rooms.insert(u);
}
/* if (comps[X].edge_cnt > comps[Y].edge_cnt) {
swap(comps[X].edges, comps[Y].edges);
swap(comps[X].edge_cnt, comps[Y].edge_cnt);
swap(comps[X].keys, comps[Y].keys);
swap(comps[X].cands, comps[Y].cands);
}*/
//if (comps[X].cands.size() > comps[Y].cands.size()) {
//swap(comps[X].cands, comps[Y].cands);
//}
for (auto k: comps[X].cands) {
comps[Y].add_cand(k);
}
comps[X].cands.clear();
//if (comps[X].keys.size() > comps[Y].keys.size()) {
swap(comps[X].keys, comps[Y].keys);
//}
for (auto k: comps[X].keys) {
comps[Y].add_key(k);
}
comps[X].keys.clear();
for (auto p: comps[X].edges) {
int k = p.first;
for (auto e: p.second) {
int u = e.first;
int v = e.second;
comps[Y].add_edge(u, v, k);
}
}
comps[X].edges.clear();
for (auto p: comps[Y].edges) {
int k = p.first;
if (comps[Y].keys.find(k) != comps[Y].keys.end()) {
assert(comps[Y].cands.find(k) != comps[Y].cands.end());
}
}
}
void expand(int X) {
if (comps[X].par != -1 || comp_id[X] != X) {
return;
}
while (!comps[X].cands.empty()) {
auto it1 = comps[X].cands.begin();
auto it2 = comps[X].edges.find(*it1);
if (it2 == comps[X].edges.end()) {
comps[X].cands.erase(it1);
continue;
}
auto it3 = it2->second.begin();
it2->second.erase(it3);
if (it2->second.empty()) {
comps[X].cands.erase(it1);
comps[X].edges.erase(it2);
}
int u = it3->first;
int v = it3->second;
if (comps[X].rooms.find(u) == comps[X].rooms.end()) {
swap(u, v);
}
if (D.root(u) != D.root(v)) {
D.join(u, v);
comps[X].par = comp_id[v];
return;
}
v = comp_id[v];
vector<int> path;
while (v != X) {
path.push_back(v);
v = comp_id[comps[v].par];
}
for (auto Y: path) {
merge(Y, X);
X = comp_id[X];
}
}
}
vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
int N = R.size();
int M = U.size();
D.init(N);
for (int i = 0; i < N; i++) {
comps[i].id = i;
comps[i].rooms.insert(i);
comp_id[i] = i;
comps[i].add_key(R[i]);
}
for (int i = 0; i < M; i++) {
comps[U[i]].add_edge(U[i], V[i], C[i]);
comps[V[i]].add_edge(U[i], V[i], C[i]);
}
while (!S.empty()) {
int X = *S.begin();
S.erase(S.begin());
expand(X);
}
int mi = N + 1;
for (int i = 0; i < N; i++) {
if (comps[comp_id[i]].par == -1) {
mi = min(mi, (int)comps[comp_id[i]].rooms.size());
}
}
vector<int> res(N);
for (int i = 0; i < N; i++) {
res[i] = (comps[comp_id[i]].par == -1 && (int)comps[comp_id[i]].rooms.size() == mi);
}
return res;
}
