#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 2000;
const int MAXK = 2000;
vector<pii> adj[MAXN + 10];
int vis[MAXN + 10];
int ok[MAXK + 10];
vector<int> ed[MAXK + 10];
int solve(int n, int s, vector<i32> &R) {
For(i, 0, n - 1) {
vis[i] = ok[i] = 0;
ed[i].clear();
}
queue<int> quer, quek;
quer.emplace(s);
vis[s] = 1;
while(sz(quer) || sz(quek)) {
if(sz(quer)) {
int cur = quer.front(); quer.pop();
if(!ok[R[cur]]) {
ok[R[cur]] = 1;
quek.emplace(R[cur]);
}
for(auto &e:adj[cur]) {
if(ok[e.S] && !vis[e.F]) {
vis[e.F] = 1;
quer.emplace(e.F);
} else if(!ok[e.S]) {
ed[e.S].eb(e.F);
}
}
}
if(sz(quek)) {
int k = quek.front(); quek.pop();
for(auto &i:ed[k]) if(!vis[i]) {
vis[i] = 1;
quer.emplace(i);
}
ed[k].clear();
}
}
int cnt = 0;
For(i, 0, n - 1) if(vis[i]) cnt++;
return cnt;
}
vector<i32> find_reachable(vector<i32> R, vector<i32> U, vector<i32> V, vector<i32> C) {
int n = sz(R);
int m = sz(C);
For(i, 0, m - 1) {
adj[U[i]].eb(V[i], C[i]);
adj[V[i]].eb(U[i], C[i]);
}
vector<int> cnt;
int mn = n + 48763;
For(i, 0, n - 1) {
cnt.eb(solve(n, i, R));
mn = min(mn, cnt.back());
}
vector<i32> ans;
For(i, 0, n - 1) {
ans.eb(cnt[i] == mn);
}
return ans;
}
/*
4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
3 1 2
0 1 1 0
7 10
0 1 1 2 2 1 2
0 1 0
0 2 0
1 2 1
1 3 0
2 3 0
3 4 1
3 5 2
4 5 0
4 6 2
5 6 1
0 1 1 0 1 0 1
3 1
0 0 0
0 1 0
0 0 1
*/
