无向图欧拉路径

【题目描述】

本题有 $T$ 组测试数据。

给定一张 无向图 $G$，由 $N$ 个顶点和 $M$ 条边组成。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。这张图不一定是简单图。

$G$ 的 欧拉路径（eulerian trail）是一对序列：顶点序列 $(v_0,\ldots,v_M)$ 与边序列 $(e_0,\ldots,e_{M-1})$，满足以下条件。

• $(e_0,\ldots,e_{M-1})$ 是 $(0, \ldots, M-1)$ 的一个排列。
• 对于 $0\leq i < M-1$，边 $e_i$ 连接 $v_i$ 和 $v_{i+1}$。

判断 $G$ 是否存在欧拉路径，若存在则输出一条。

【输入】

$T$
$N$ $M$
$u_0$ $v_0$
$\vdots$
$u_{M-1}$ $v_{M-1}$
$N$ $M$
$u_0$ $v_0$
$\vdots$
$u_{M-1}$ $v_{M-1}$
$\vdots$

【输出】

如果不存在欧拉路径，输出 No。否则按以下格式输出一条欧拉路径。

Yes
$v_0$ $\ldots$ $v_{M}$
$e_0$ $\ldots$ $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

【输入样例2】

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

【输出样例2】

Yes
0

Yes
0 1
0
Yes
4 4
0
No

【数据范围】

• $1 \leq T \leq 100000$
• $1 \leq N \leq 200000$
• $0 \leq M \leq 200000$
• $0 \leq u_i, v_i \lt N$
• 所有测试数据的 $N$ 之和不超过 $200000$。
• 所有测试数据的 $M$ 之和不超过 $200000$。

【来源】

Library Checker（yosupo06） eulerian_trail_undirected

本题为 special judge（输出任意合法解），暂不可本地评测。