#include <bits/stdc++.h>

using namespace std;

struct UnionFind {
  vector<int> fa;
  UnionFind(int n) : fa(n, -1) {}
  bool isRoot(int u) { return !~fa[u]; }
  int find(int u) { return isRoot(u) ? u : fa[u] = find(fa[u]); }
  void mergeTo(int u, int v) {
    int fu = find(u), fv = find(v);
    if (fu == fv) return ;
    fa[fu] = fv;
  }
};

vector<int> find_reachable(vector<int> a, vector<int> u, vector<int> v, vector<int> c) {
  int n = a.size(), m = u.size();
  vector<vector<pair<int, int>>> e(n);
  for (int i = 0; i < m; ++i) e[u[i]].emplace_back(v[i], c[i]), e[v[i]].emplace_back(u[i], c[i]);
  vector<int> ans; int minv = n + 1; UnionFind uf(n);
  bool flag; vector<int> ers(n);
  do {
    flag = 0; vector<int> vis(n);
    vector<int> withKey(n);
    vector<vector<int>> waitKey(n);
    auto bfs = [&](int s) {
      vector<int> vec; queue<int> q;
      vector<int> t0, t1;
      bool found = 0;
      q.push(s);
      while (!q.empty()) {
        int u = q.front(); q.pop();
        if (uf.find(u) != s) {
          uf.mergeTo(s, u), vis[uf.find(u)] = 1, found = 1;
          break;
        }
        if (vis[u]) continue;
        vis[u] = 1, vec.push_back(u);
        withKey[a[u]] = 1, t0.push_back(a[u]);
        for (int v : waitKey[a[u]]) q.push(v);
        waitKey[a[u]].clear();
        for (auto [v, w] : e[u])
          if (withKey[w]) q.push(v);
          else t1.push_back(w), waitKey[w].push_back(v);
      }
      for (int i : t0) withKey[i] = 0;
      for (int i : t1) waitKey[i].clear();
      if (!found) {
        if (vec.size() < minv) minv = vec.size(), ans = vec;
        else if (vec.size() == minv) ans.insert(ans.end(), vec.begin(), vec.end());
        ers[s] = 1;
      }
    };
    for (int s = 0; s < n; ++s)
      if (uf.isRoot(s) && !vis[s] && !ers[s]) bfs(s), flag = 1;
  } while (flag);
  vector<int> ret(n);
  for (int i : ans) ret[i] = 1;
  return ret;
}