#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int increment = 0, n = 0, m = 0;
vector<int> assigned_key, mutex, depth;
vector<pair<int, int>> vertex_onion, key_onion;
vector<vector<pair<int, int>>> edge;
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() {
increment = 0;
for(auto& i : mutex) i = 0;
for(auto& i : depth) i = 0;
}
int dfs(int x) {
if(mutex[x] == 1) return depth[x];
if(mutex[x] == 2) return -1;
mutex[x] = 1;
depth[x] = increment;
increment++;
for(auto i : edge[x]) {
if(get_root(assigned_key[x], key_onion) == get_root(i.second, key_onion)) {
int val = dfs(i.first);
if(depth[x] > val && val != -1)
depth[x] = val;
}
}
mutex[x] = 2;
return depth[x];
}
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++)
key_onion[i].first = vertex_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]});
}
for(int step = 0; step < 20; step++) {
dfs_init();
vector<vector<int>> counting;
counting.resize(n, {});
for(int i = 0; i < n; i++) dfs(i);
for(int i = 0; i < n; i++)
counting[depth[i]].push_back(i);
for(int i = 0; i < n; i++) {
if(counting[i].size() < 2) continue;
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;
}
