#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2020;
int n;
int R[N];
bool vis1[N];
bool vis2[N];
bool have[N];
queue<int> q1;
queue<int> q2[N];
vector<pii> adj[N];
void clear(queue<int>& q) {
while (!q.empty()) {
q.pop();
}
}
int count(int x) {
memset(vis1, false, sizeof(vis1));
memset(vis2, false, sizeof(vis2));
memset(have, false, sizeof(have));
clear(q1);
for (int i = 0; i < n; i++) {
clear(q2[i]);
}
q1.push(x);
int answer = 0;
while (!q1.empty()) {
int x = q1.front();
q1.pop();
if (vis1[x]) {
continue;
}
answer++;
vis1[x] = true;
if (!have[R[x]]) {
have[R[x]] = true;
while (!q2[R[x]].empty()) {
int y = q2[R[x]].front();
q2[R[x]].pop();
q1.push(y);
}
}
for (const pii& p : adj[x]) {
int y = p.first, w = p.second;
if (!vis1[y]) {
if (have[w]) {
q1.push(y);
} else {
q2[w].push(y);
}
}
}
}
return answer;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n = r.size();
int m = u.size();
for (int i = 0; i < n; i++) {
R[i] = r[i];
}
for (int j = 0; j < m; j++) {
adj[u[j]].emplace_back(v[j], c[j]);
adj[v[j]].emplace_back(u[j], c[j]);
}
vector<int> answer(n);
for (int i = 0; i < n; i++) {
answer[i] = count(i);
}
int minimum = *min_element(answer.begin(), answer.end());
for (int& x : answer) {
x = (x == minimum);
}
return answer;
}
