#include <cstdio>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
int increment = 0;
int cnt = 0;
vector<vector<int>> room_group_keys;
vector<vector<int>> room_group_rooms;
vector<vector<pair<int, int>>> connector;
vector<int> stack;
vector<int> mutex, depth;
void dfs_init() {
int s = room_group_keys.size();
stack.clear();
increment = 0;
mutex.resize(s);
for(auto& i : mutex) i = 0;
depth.resize(s);
for(auto& i : depth) i = 0;
}
void dfs(int x) {
if(mutex[x] == 1) return;
mutex[x] = 1;
for(auto i : connector[x]) {
if(binary_search(room_group_keys[x].begin(), room_group_keys[x].end(), i.second))
dfs(i.first);
}
stack.push_back(x);
}
bool rdfs(int x) {
if(mutex[x] == 2) return false;
mutex[x] = 2;
depth[x] = increment;
for(auto i : connector[x]) {
if(binary_search(room_group_keys[i.first].begin(), room_group_keys[i.first].end(), i.second))
rdfs(i.first);
}
return true;
}
void dfs_final(int x, vector<int>& logging) {
if(mutex[x] == 1)
return;
mutex[x] = 1;
for(auto i : connector[x]) {
if(binary_search(room_group_keys[x].begin(), room_group_keys[x].end(), i.second)) {
if(x != i.first)
logging[x] = false;
dfs_final(i.first, logging);
}
}
}
vector<int> find_reachable_internal() {
cnt++;
if(cnt >= 20)
printf("%d, You are wrong by tentacles!\n", cnt);
int prev = room_group_keys.size();
// To-do: construct SCC
dfs_init();
for(int i = 0; i < room_group_keys.size(); i++) dfs(i);
while(stack.size()) {
int top = stack.back();
if(rdfs(top))
increment++;
stack.pop_back();
}
// Report result (if SCC is equal with graph)
if(prev == increment) {
dfs_init();
vector<int> logging;
logging.resize(prev, true);
for(int i = 0; i < prev; i++)
dfs_final(i, logging);
int min_size = 1e9, sum = 0;
for(int i = 0; i < prev; i++) {
int s = room_group_rooms[i].size();
sum += s;
if(min_size > s && logging[i])
min_size = s;
}
vector<int> ans;
ans.resize(sum, 0);
for(int i = 0; i < prev; i++) {
int s = room_group_rooms[i].size();
if(min_size != s || !logging[i])
continue;
for(auto j : room_group_rooms[i]) {
ans[j] = 1;
}
}
return ans;
}
// Query (if SCC is smaller than graph)
vector<vector<int>> new_room_group_keys;
vector<vector<int>> new_room_group_rooms;
vector<vector<pair<int, int>>> new_connector;
new_room_group_keys.resize(increment, {});
new_room_group_rooms.resize(increment, {});
new_connector.resize(increment, {});
for(int i = 0; i < prev; i++) {
for(auto j : room_group_keys[i])
new_room_group_keys[depth[i]].push_back(j);
for(auto j : room_group_rooms[i])
new_room_group_rooms[depth[i]].push_back(j);
for(auto j : connector[i]) {
if(depth[i] != depth[j.first])
new_connector[depth[i]].push_back({depth[j.first], j.second});
}
}
for(int i = 0; i < increment; i++)
sort(new_room_group_keys[i].begin(), new_room_group_keys[i].end());
room_group_keys.swap(new_room_group_keys);
room_group_rooms.swap(new_room_group_rooms);
connector.swap(new_connector);
return find_reachable_internal();
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
// vector<vector<int>> room_group_keys, vector<vector<int>> room_group_rooms, vector<vector<pair<int, int>>> connector
int n = r.size(), m = u.size();
connector.resize(n, {});
for(int i = 0; i < n; i++) {
room_group_keys.push_back({r[i]});
room_group_rooms.push_back({i});
}
for(int i = 0; i < m; i++) {
connector[u[i]].push_back({v[i], c[i]});
connector[v[i]].push_back({u[i], c[i]});
}
for(int i = 0; i < n; i++)
std::sort(room_group_keys[i].begin(), room_group_keys[i].end());
return find_reachable_internal();
}
