#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<vector<pair<int, int>>> adj;
vector<int> R, C;
vector<int> visited;
int find_size(int index)
{
set<int> keys;
map<int, vector<int>> locked;
vector<int> visited(N);
stack<int> stck;
stck.push(index);
int cnt = 0;
while (!stck.empty())
{
int s = stck.top();
stck.pop();
if (visited[s]) continue;
visited[s] = 1;
cnt++;
if (!keys.count(R[s]))
{
keys.insert(R[s]);
for (auto node : locked[R[s]])
{
if (!visited[node])
stck.push(node);
}
}
for (auto node : adj[s])
{
if (visited[node.first]) continue;
if (keys.count(node.second))
stck.push(node.first);
else
locked[node.second].push_back(node.first);
}
}
return cnt;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
R = r; C = c;
N = r.size(); M = u.size();
adj = vector<vector<pair<int, int>>>(N);
for (int i = 0; i < M; i++)
{
adj[u[i]].push_back({v[i], c[i]});
adj[v[i]].push_back({u[i], c[i]});
}
vector<int> sz(N);
int mn_sz = 1 << 30;
for (int i = 0; i < N; i++)
{
sz[i] = find_size(i);
mn_sz = min(mn_sz, sz[i]);
}
vector<int> ans(N);
for (int i = 0; i < N; i++)
ans[i] = (sz[i] == mn_sz);
return ans;
}
