#include <vector>
#include "keys.h"
#define F first
#define S second
using namespace std;
const int N = 2e3 + 10;
int n , m , col[N] , p[N];
vector <pair<int , int>> adj[N];
bool marked[N] , key[N];
vector <int> to[N] , can;
void Add_vert(int v)
{
for(auto u : adj[v])
{
if(key[u.F])
can.push_back(u.S);
else
to[u.F].push_back(u.S);
}
}
void Add_col(int v)
{
for(auto u : to[v])
can.push_back(u);
to[v].clear();
}
void Solve(int star)
{
vector <int> all;
all.push_back(star);
marked[star] = true;
while(!all.empty())
{
int v = all.back(); all.pop_back();
key[col[v]] = true;
Add_vert(v);
Add_col(col[v]);
while(!can.empty())
{
int u = can.back(); can.pop_back();
if(!marked[u])
{
marked[u] = true;
all.push_back(u);
}
}
}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n = r.size();
m = u.size();
for(int i = 0 ; i < n ; i++)
col[i] = r[i];
for(int i = 0 ; i < m ; i++)
{
adj[u[i]].push_back(make_pair(c[i] , v[i]));
adj[v[i]].push_back(make_pair(c[i] , u[i]));
}
int mn = N;
for(int i = 0 ; i < n ; i++)
{
Solve(i);
p[i] = 0;
for(int j = 0 ; j < n ; j++)
{
p[i] += marked[j];
marked[j] = false;
key[j] = false;
to[j].clear();
}
mn = min(mn , p[i]);
}
vector <int> ans(n);
for(int i = 0 ; i < n ; i++)
{
if(p[i] == mn)
ans[i] = 1;
else
ans[i] = 0;
}
return ans;
}
