#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#include "keys.h"
using namespace std;
const int maxn = 3e5 + 3;
vector <pair <int, int> > adj_all[maxn];
vector <int> adj[maxn], adj_rev[maxn];
vector <int> order;
bool used[maxn];
unordered_set <int> keys[maxn];
int par[maxn], sz[maxn];
inline int find_root(int ver) {
if (ver == par[ver])
return ver;
return par[ver] = find_root(par[ver]);
}
void merge(int a, int b) {
a = find_root(a), b = find_root(b);
if (a == b)
return;
if (sz[a] < sz[b])
swap(a, b);
for (auto i: keys[b])
keys[a].insert(i);
sz[a] += sz[b];
par[b] = a;
}
void dfs(int ver) {
used[ver] = true;
for (auto i: adj[ver])
if (!used[i])
dfs(i);
order.push_back(ver);
}
void dfs_rev(int ver, int root) {
merge(ver, root);
used[ver] = true;
for (auto i: adj_rev[ver])
if (!used[i])
dfs_rev(i, root);
}
vector <int> comp[maxn];
vector <int> find_reachable(vector <int> r, vector <int> u, vector <int> v, vector <int> c) {
int n = (int)r.size(), m = (int)u.size();
for (int i = 0; i < m; i++) {
adj_all[v[i]].push_back(make_pair(u[i], c[i]));
adj_all[u[i]].push_back(make_pair(v[i], c[i]));
}
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
keys[i].insert(r[i]);
}
for (int iter = 1; iter <= 20; iter++) {
for (int i = 0; i < n; i++) {
adj[i].clear();
adj_rev[i].clear();
}
for (int i = 0; i < n; i++) {
int root = find_root(i);
for (auto j: adj_all[i])
if (keys[root].find(j.second) != keys[root].end()) {
adj[root].push_back(find_root(j.first));
adj_rev[find_root(j.first)].push_back(root);
}
}
memset(used, false, sizeof(used));
order.clear();
for (int i = 0; i < n; i++)
if (i == find_root(i) && !used[i])
dfs(i);
memset(used, false, sizeof(used));
reverse(order.begin(), order.end());
for (auto i: order)
if (!used[i])
dfs_rev(i, i);
}
int mins = INT_MAX;
vector <int> smallest;
for (int i = 0; i < n; i++)
comp[find_root(i)].push_back(i);
for (int i = 0; i < n; i++)
if (!comp[i].empty()) {
bool is = true;
for (auto j: comp[i])
for (auto k: adj_all[j])
if (keys[i].find(k.second) != keys[i].end())
if (find_root(k.first) != i) {
is = false;
break;
}
if (is) {
if ((int)comp[i].size() < mins) {
mins = comp[i].size();
smallest.clear();
}
if ((int)comp[i].size() == mins)
for (auto j: comp[i])
smallest.push_back(j);
}
}
vector <int> ans(n, false);
for (auto i: smallest)
ans[i] = true;
return ans;
}
/*
int n, m;
vector <int> r, u, v, c;
int main() {
cin >> n >> m;
r.resize(n), u.resize(m), v.resize(m), c.resize(m);
for (int i = 0; i < n; i++)
cin >> r[i];
for (int i = 0; i < m; i++)
cin >> u[i] >> v[i] >> c[i];
auto ans = find_reachable({0, 1, 1, 2, 2, 1, 2},{0, 0, 1, 1, 2, 3, 3, 4, 4, 5},{1, 2, 2, 3, 3, 4, 5, 5, 6, 6},{0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
for (auto i: ans)
cout << i << " ";
cout << endl;
}
*/
/*
4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
3 1 2
*/
