#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<vector<int>> adj;
vector<int> visited;
int DFS(int index)
{
visited[index] = 1;
int sz = 0;
for (auto node : adj[index])
{
if (visited[node]) continue;
sz += DFS(node);
}
return sz + 1;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
N = r.size(); M = u.size();
adj = vector<vector<int>>(N);
for (int i = 0; i < M; i++)
{
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
vector<int> ans(N);
int ok = false;
for (int i = 0; i < N; i++)
{
if (r[i] || adj[i].size() == 0)
{
ans[i] = 1;
ok = true;
}
}
if (ok)
return ans;
visited = vector<int>(N);
int mn_size = 1 << 30;
vector<int> min_components;
for (int i = 0; i < N; i++)
{
if (visited[i]) continue;
int sz = DFS(i);
if (sz < mn_size)
{
min_components = {};
mn_size = sz;
}
if (sz == mn_size)
min_components.push_back(i);
}
visited = vector<int>(N);
for (auto node : min_components)
{
DFS(node);
}
return visited;
}
