#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
struct grana {
int x, y, c;
};
struct cvor {
vector<int> v;
set<int> c;
};
struct bidigraf {
vector<cvor> v;
vector<grana> e;
};
struct digraf {
vector<vi> e;
vi idx, low, inst, st;
int dt;
vector<vi> comps;
void dfs(int x) {
idx[x] = low[x] = ++dt;
inst[x] = 1;
st.push_back(x);
for (int y : e[x]) {
if (idx[y] == 0) {
dfs(y);
low[x] = min(low[x], low[y]);
} else if (inst[y]) {
low[x] = min(low[x], idx[y]);
}
}
if (idx[x] == low[x]) {
vi comp;
while (1) {
int t = st.back();
st.pop_back();
inst[t] = 0;
comp.push_back(t);
if (t == x) {
break;
}
}
comps.push_back(comp);
}
}
void scc() {
dt = 0;
const int n = e.size();
low = inst = idx = vi(n);
st = {};
comps = {};
for (int i=0; i<n; i++) {
if (!idx[i]) {
dfs(i);
}
}
}
vi rikverc(const vi& b) {
const int n = e.size();
vector<vi> f(n);
for (int i=0; i<n; i++) {
for (int j : e[i]) {
f[j].push_back(i);
}
}
vi q, vis(n);
size_t qs = 0;
for (int x : b) {
q.push_back(x);
vis[x] = 1;
}
while (qs != q.size()) {
int x = q[qs++];
for (int y : f[x]) {
if (!vis[y]) {
vis[y] = 1;
q.push_back(y);
}
}
}
return vis;
}
};
vector<vi> naj;
void prijavi(const vi& a) {
if (naj.empty() || naj[0].size() == a.size()) {
naj.push_back(a);
} else if (naj[0].size() > a.size()) {
naj = {a};
}
}
void resi(const bidigraf& bd) {
// napravi prvo digraf
digraf d;
const int n = bd.v.size();
d.e.resize(n);
for (auto [x, y, c] : bd.e) {
if (bd.v[x].c.count(c)) {
d.e[x].push_back(y);
}
if (bd.v[y].c.count(c)) {
d.e[y].push_back(x);
}
}
vi rikverc;
// ima izolovanih cvorova?
for (int i=0; i<n; i++) {
if (d.e[i].empty()) {
rikverc.push_back(i);
prijavi(bd.v[i].v);
}
}
d.scc();
auto vis = d.rikverc(rikverc);
bidigraf mali;
vi mapa(n, -1);
for (const auto& comp : d.comps) {
if (vis[comp[0]]) continue;
cvor t;
for (int x : comp) {
const auto& cx = bd.v[x].c;
const auto& vx = bd.v[x].v;
t.c.insert(cx.begin(), cx.end());
t.v.insert(t.v.end(), vx.begin(), vx.end());
mapa[x] = (int)mali.v.size();
}
mali.v.emplace_back(move(t));
}
for (auto [x, y, c] : bd.e) {
if (mapa[x] != -1 && mapa[y] != -1 && mapa[x] != mapa[y]) {
mali.e.push_back({mapa[x], mapa[y], c});
}
}
if (!mali.v.empty()) {
resi(mali);
}
}
vi izvestaj(int n) {
vi a(n);
for (const auto& v : naj) {
for (int x : v) {
a[x] = 1;
}
}
return a;
}
vi find_reachable(vi r, vi u, vi v, vi c) {
bidigraf bd;
const int n = r.size();
const int m = u.size();
bd.v.resize(n);
bd.e.resize(m);
for (int i=0; i<n; i++) {
bd.v[i] = {{i}, {r[i]}};
}
for (int i=0; i<m; i++) {
bd.e[i] = {u[i], v[i], c[i]};
}
resi(bd);
return izvestaj(n);
}
