Taka 与 HashiAI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)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.
Takahashi 因能够分裂成著名的搞笑二人组合“Taka 与 Hashi”而闻名，也就是说，他可以分裂成 Taka 和 Hashi。当 Taka 与 Hashi 合并时，他们会恢复成原来的 Takahashi。
给定一个有 $N$ 个顶点和 $M$ 条边的连通无向图，每条边都标记为 $1$、$2$ 或 $3$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，标记为 $l_i$。图中不包含自环，但可能包含重边。
每条边只能由 Takahashi、Taka 和 Hashi 中的一人通过；标记为 $1$、$2$ 或 $3$ 的边分别只能由 Takahashi、Taka 或 Hashi 通过。
初始时，Takahashi 位于顶点 $1$。Takahashi 和其他人可以按照任意顺序执行以下操作任意次，也可以一次都不执行。
- Takahashi 在当前所在的顶点分裂成 Taka 和 Hashi。此时，Taka 和 Hashi 都位于该顶点。
- 当前存在的某个人通过一条自己能够通过的边移动。
- 当 Taka 和 Hashi 位于同一顶点时，他们在该顶点合并，恢复成 Takahashi。
请按升序列出执行一系列操作后 Takahashi 可能所在的所有顶点。
给定 $T$ 个测试用例，请分别求解每个测试用例。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$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 \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$。 - 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入给出，格式如下：AI (CI翻译)
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_TT
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_TEach test case $\mathrm{case}_t$ is given in the following format:
每个测试用例 $\mathrm{case}_t$ 的格式如下：AI (CI翻译)
N M
u_1 v_1 l_1
u_2 v_2 l_2
\vdots
u_M v_M l_MN M
u_1 v_1 l_1
u_2 v_2 l_2
\vdots
u_M v_M l_MOutput
输出格式
AI (CI翻译)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样例
3
5 5
1 2 1
2 3 2
3 4 2
2 4 3
4 5 1
8 15
1 3 3
1 5 2
1 5 3
1 7 1
2 3 2
2 4 1
2 5 3
2 6 1
2 7 3
2 8 1
3 4 3
3 5 3
4 7 2
5 6 1
6 7 1
10 13
1 3 2
1 4 1
1 6 1
2 7 2
2 8 2
3 6 2
3 9 2
4 5 3
4 7 2
4 9 2
5 8 2
5 10 3
6 7 2
4
1 2 4 5
8
1 2 3 4 5 6 7 8
4
1 4 5 6
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。