AT_arc229_e.Taka and Hashi

Takahashi is known for being able to split into the famous comedy duo "Taka and Hashi", that is, Taka and Hashi. When Taka and Hashi merge, they return to being the original Takahashi.
There is a connected undirected graph with $N$ vertices and $M$ edges, and each edge is labeled with $1$, $2$, or $3$. The $i$-th edge connects vertices $u_i$ and $v_i$, and is labeled $l_i$. The graph does not contain self-loops, but may contain multi-edges.
Each edge can be traversed by only one of Takahashi, Taka, and Hashi, and an edge labeled $1$, $2$, or $3$ can be traversed only by Takahashi, Taka, or Hashi, respectively.

Initially, Takahashi is at vertex $1$. Takahashi and the others can perform the following operations in any order, zero or more times.

• Takahashi splits into Taka and Hashi at the vertex where he currently is. At this point, both Taka and Hashi are at that vertex.
• One of the currently existing people moves by traversing one edge that they are able to traverse.
• When Taka and Hashi are at the same vertex, they merge at that vertex and return to being Takahashi.

Enumerate, in ascending order, all vertices where Takahashi can be after performing a sequence of operations.

You are given $T$ test cases; solve each of them.

高桥以能分裂成著名搞笑组合“塔卡与哈希”（即塔卡和哈希）而闻名。当塔卡与哈希合并时，他们便恢复为原来的高桥。
现有一个包含 $N$ 个顶点和 $M$ 条边的连通无向图，每条边被标记为 $1$、$2$ 或 $3$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，其标记为 $l_i$。该图不含自环，但可能含重边。
每条边仅能由高桥、塔卡或哈希中的一人 traversed（通行），且标记为 $1$、$2$ 或 $3$ 的边分别只能由高桥、塔卡或哈希通行。

初始时，高桥位于顶点 $1$。高桥及其他人员可按任意顺序执行以下操作零次或多次：

• 高桥在当前所在顶点分裂为塔卡和哈希；此时塔卡和哈希均位于该顶点。
• 当前存在的某一人沿一条其可通行的边移动一步。
• 当塔卡与哈希处于同一顶点时，他们在该顶点合并，并恢复为高桥。

请按升序枚举所有高桥经过一系列操作后可能到达的顶点。

你将得到 $T$ 组测试用例，请对每组用例求解。

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case $\mathrm{case}_t$ is given in the following format:

$N$ $M$
$u_1$ $v_1$ $l_1$
$u_2$ $v_2$ $l_2$
$\vdots$
$u_M$ $v_M$ $l_M$

输入从标准输入中按以下格式给出：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例 $\mathrm{case}_t$ 按以下格式给出：

$N$ $M$
$u_1$ $v_1$ $l_1$
$u_2$ $v_2$ $l_2$
$\vdots$
$u_M$ $v_M$ $l_M$

Output $2T$ lines.
For each test case, letting $a_1,a_2,\dots,a_k$ be the sequence of numbers of the vertices satisfying the condition, listed in ascending order, output them in the following format:

$k$
$a_1$ $a_2$ $\dots$ $a_k$

输出 $2T$ 行。
对于每个测试用例，设满足条件的顶点编号序列为 $a_1,a_2,\dots,a_k$（按升序排列），则按以下格式输出：

$k$
$a_1$ $a_2$ $\dots$ $a_k$

Sample 1 Explanation:
Consider the first test case.
Takahashi can move from vertex $1$ to vertex $2$ by traversing an edge labeled $1$. After splitting into Taka and Hashi at vertex $2$, Taka moves $2 \to 3 \to 4$ and Hashi moves $2 \to 4$, and by merging at vertex $4$, it is possible to make Takahashi be at vertex $4$. Furthermore, Takahashi can move to vertex $5$ by traversing an edge labeled $1$.
It is impossible to make Takahashi be at vertex $3$, so the vertices satisfying the condition are $1,2,4,5$.

Constraints

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $N-1 \leq M \leq 2 \times 10^5$
• $1 \leq u_i \lt v_i \leq N$
• $1 \leq l_i \leq 3$
• The given graph is connected.
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• The sum of $M$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

样例 1 解释：
考虑第一个测试用例。
高桥可以从顶点 $1$ 出发，经过一条标号为 $1$ 的边到达顶点 $2$。在顶点 $2$ 处分裂为“Taka”和“Hashi”后，“Taka”沿路径 $2 \to 3 \to 4$ 移动，而“Hashi”沿路径 $2 \to 4$ 移动；二者在顶点 $4$ 处合并，从而使得高桥最终位于顶点 $4$。此外，高桥还可通过一条标号为 $1$ 的边从当前所在顶点移动至顶点 $5$。
无法使高桥到达顶点 $3$，因此满足条件的顶点为 $1,2,4,5$。

限制条件

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $N-1 \leq M \leq 2 \times 10^5$
• $1 \leq u_i \lt v_i \leq N$
• $1 \leq l_i \leq 3$
• 给定图是连通的。
• 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$。
• 所有测试用例中 $M$ 的总和不超过 $2 \times 10^5$。
• 所有输入值均为整数。