CF1994F Stardew Valley

Pelican Town 有 $n$ 个房屋，通过 $m$ 条双向道路相连。有些道路上站着 NPC。农夫 Buba 需要走过每一条有 NPC 的道路，并与他们交谈。 请帮助农夫找到一条满足以下条件的路线： - 路线从某个房屋出发，沿着道路行走，最终回到同一个房屋。 - 路线不会重复经过任何一条道路（无论方向）。 - 路线恰好经过每一条有 NPC 的道路一次。 注意，路线可以经过没有 NPC 的道路，并且不需要使路线最短。保证仅通过有 NPC 的道路可以从任意房屋到达任意其他房屋。

每个测试包含多个测试用例。第一行为一个整数 $t$（$1 \le t \le 10^{4}$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 5 \cdot 10^5, 1 \leq m \leq 5 \cdot 10^5$），分别表示 Pelican Town 的房屋数和道路数。 接下来的 $m$ 行，每行包含三个整数 $u$、$v$ 和 $c$（$1 \leq u, v \leq n, c = 0/1$），表示道路的两个端点和该道路上是否有 NPC。如果 $c = 1$，则该道路上有 NPC；如果 $c = 0$，则该道路上没有 NPC。 图中可能存在重边和自环。如果有多条有 NPC 的重边，路线必须分别经过每一条。 保证仅通过有 NPC 的道路可以从任意房屋到达任意其他房屋。 保证所有测试用例中 $n$ 和 $m$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，如果无解，输出 "No"（不带引号）。 否则，输出 "Yes"（不带引号），然后输出 $k$ —— 路线经过的道路数。下一行输出 $k + 1$ 个数字，表示路线经过的房屋编号，按顺序输出。注意，首尾房屋编号应相同，因为路线是一个回路。 如果有多种答案，可以输出任意一种。 输出时字母大小写均可（例如 "yEs"、"yes"、"Yes"、"YES" 都视为正解）。

注意，在第三个测试用例中，存在多条 $(5, 2)$ 的重边。你必须分别走过这两条道路。 由 ChatGPT 4.1 翻译