无向图欧拉迹（Eulerian Trail (Undirected)）

问题描述

本题有 $T$ 组测试数据。
对每组，给定一个含 $N$ 个顶点、$M$ 条边的无向图 $G$（可能含重边，无自环），判断是否存在欧拉迹（Eulerian trail）——即一条经过每条边恰好一次的路径。

若存在，输出任意一条欧拉迹：

• 顶点序列 $v_0, v_1, \dots, v_M$（长度 $M+1$）
• 边序列 $e_0, e_1, \dots, e_{M-1}$（长度 $M$），其中 $e_i$ 是路径中第 $i$ 条边的输入索引，且 $e_0,\dots,e_{M-1}$ 是 $\{0,1,\dots,M-1\}$ 的一个排列，满足边 $e_i$ 连接 $v_i$ 与 $v_{i+1}$。

若不存在，输出 No。

约束条件

• $1 \leq T \leq 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• 所有测试用例中 $\sum N \leq 2 \times 10^5$，$\sum M \leq 2 \times 10^5$

输入

$T$
$N\ M$
$u_0\ v_0$
$u_1\ v_1$
:
$u_{M-1}\ v_{M-1}$
（重复 $T$ 组）

输出

• 若无欧拉迹：

  No

• 否则：

  Yes
  $v_0\ v_1\ \cdots\ v_M$
  $e_0\ e_1\ \cdots\ e_{M-1}$

3
4 7
0 1
0 2
0 2
0 3
1 3
2 3
3 3
4 6
0 1
0 2
0 3
1 2
1 3
2 3
6 10
0 3
1 2
4 0
5 1
4 4
2 3
1 3
3 2
1 4
5 1

Yes
2 0 1 3 0 2 3 3
2 0 4 3 1 5 6
No
Yes
1 2 3 0 4 4 1 5 1 3 2
1 7 0 2 4 8 9 3 6 5

4
10 0
10 1
0 1
10 1
4 4
10 2
4 4
5 5

Yes
0

Yes
0 1
0
Yes
4 4
0
No