Consider how Takahashi moves. When Takahashi appears at vertex \(b\) right after vertex \(a\), it can be seen that this occurs in one of the following two ways:

• He himself traverses edge \(ab\) and moves from \(a\) to \(b\), or
• He splits at vertex \(a\), and Taka and Hashi both move to vertex \(b\) and merge there.

Thus, letting the auxiliary graph \(G_1\) be the graph with edges drawn between

• the two endpoints of an edge that Takahashi can traverse, and
• pairs of vertices \((a,b)\) satisfying the following condition:
  • both Taka and Hashi, starting from vertex \(a\), can each reach vertex \(b\) via edges that they themselves can traverse, without merging along the way,

the answer is the set of vertices connected to vertex \(1\) in \(G_1\).
Therefore, the answer can be found by constructing a graph that is equivalent to \(G_1\) in terms of connectivity. This can be computed by letting the auxiliary graphs \(G_2\) and \(G_3\) be the graphs with only the edges labeled \(2\) and labeled \(3\), respectively, constructing the Union-Find structures \(U_2\) and \(U_3\) corresponding to \(G_2\) and \(G_3\), and focusing on (U_2.leader(i), U_3.leader(i)).
The time complexity is \(\mathrm{O}((N+M) \alpha(N))\) or something similar, which is fast enough.

• Sample implementation (C++)

#include <iostream>
#include <map>
#include <utility>
#include <vector>
using namespace std;

#include "atcoder/dsu.hpp"

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int T;
  cin >> T;
  while (T--) {
    int N, M;
    cin >> N >> M;
    atcoder::dsu uf1(N), uf2(N), uf3(N);
    for (int i = 0; i < M; i++) {
      int u, v, l;
      cin >> u >> v >> l;
      --u, --v;
      (l == 1 ? uf1 : l == 2 ? uf2 : uf3).merge(u, v);
    }

    map<pair<int, int>, int> mp;
    for (int i = 0; i < N; i++) {
      auto p = make_pair(uf2.leader(i), uf3.leader(i));
      if (mp.count(p)) uf1.merge(mp[p], i);
      mp[p] = i;
    }

    vector<int> ans;
    for (int i = 0; i < N; i++) {
      if (uf1.same(0, i)) ans.push_back(i + 1);
    }
    cout << ans.size() << "\n";
    for (int i = 0; i < (int)ans.size(); i++) {
      cout << ans[i] << " \n"[i + 1 == (int)ans.size()];
    }
  }
}