#include <cstdio>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
int n = 0, m = 0;
vector<int> assigned_key, mutex, depth;
vector<pair<int, int>> vertex_onion, key_onion;
vector<vector<pair<int, int>>> edge;
deque<int> hamburger;
int get_root(int x, vector<pair<int, int>>& onion) {
if(onion[x].first == x) return onion[x].first;
onion[x].first = get_root(onion[x].first, onion);
return onion[x].first;
}
void big_onion(int x, int y, vector<pair<int, int>>& onion) {
int root = get_root(x, onion), beet = get_root(y, onion);
if(root == beet) return;
if(onion[root].second < onion[beet].second)
onion[root].first = beet;
else if(onion[root].second > onion[beet].second)
onion[beet].first = root;
else {
onion[root].first = beet;
onion[beet].second++;
}
}
void dfs_init() {
hamburger.clear();
for(auto& i : mutex) i = 0;
for(auto& j : depth) j = 0;
}
void dfs(int x) {
if(mutex[x] == 1) return;
mutex[x] = 1;
for(auto i : edge[x]) {
if(get_root(assigned_key[x], key_onion) == get_root(i.second, key_onion))
dfs(i.first);
}
hamburger.push_back(x);
}
void reverse_dfs(int x, int id) {
if(mutex[x] == 2) return;
mutex[x] = 2;
depth[x] = id;
for(auto i : edge[x]) {
if(get_root(assigned_key[i.first], key_onion) == get_root(i.second, key_onion))
reverse_dfs(i.first, id);
}
}
void dfs_final(int x, vector<int>& log) {
if(mutex[x]) return;
mutex[x] = 1;
for(auto i : edge[x]) {
if(get_root(assigned_key[x], key_onion) == get_root(i.second, key_onion)) {
if(get_root(x, vertex_onion) != get_root(i.first, vertex_onion))
log[get_root(x, vertex_onion)] = true;
dfs_final(i.first, log);
}
}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n = r.size(), m = u.size();
vertex_onion.resize(n, {0, 0});
key_onion.resize(n, {0, 0});
edge.resize(n, {});
mutex.resize(n, 0);
depth.resize(n, 0);
assigned_key = r;
for(int i = 0; i < n; i++)
vertex_onion[i].first = key_onion[i].first = i;
for(int i = 0; i < m; i++) {
edge[u[i]].push_back({v[i], c[i]});
edge[v[i]].push_back({u[i], c[i]});
}
int prev = n, curr = 0;
while(prev != curr) {
prev = curr;
curr = 0;
int increment = 0;
dfs_init();
vector<vector<int>> counting;
counting.resize(n, {});
for(int i = 0; i < n; i++) dfs(i);
while(hamburger.size()) {
int top = hamburger.back();
reverse_dfs(top, increment);
hamburger.pop_back();
increment++;
}
for(int i = 0; i < n; i++)
counting[depth[i]].push_back(i);
for(int i = 0; i < n; i++) {
if(counting[i].empty()) continue;
curr++;
for(int j = 1; j < counting[i].size(); j++) {
big_onion(counting[i][j - 1], counting[i][j], vertex_onion);
big_onion(assigned_key[counting[i][j - 1]], assigned_key[counting[i][j]], key_onion);
}
}
}
final_tentacular_boss:
vector<int> ans;
vector<vector<int>> counting;
vector<int> log;
ans.resize(n, 0);
log.resize(n, 0);
counting.resize(n, {});
dfs_init();
for(int i = 0; i < n; i++) dfs_final(i, log);
for(int i = 0; i < n; i++) {
if(log[get_root(i, vertex_onion)]) continue;
counting[get_root(i, vertex_onion)].push_back(i);
}
int min_size = 1e9;
for(int i = 0; i < n; i++) {
if(counting[i].empty()) continue;
if(min_size > counting[i].size())
min_size = counting[i].size();
}
for(int i = 0; i < n; i++) {
if(counting[i].empty()) continue;
if(min_size == counting[i].size())
for(auto j : counting[i])
ans[j] = 1;
}
return ans;
}
