有向图欧拉路径

【题目描述】

本题包含 $T$ 组测试数据。

给定一个由 $N$ 个顶点和 $M$ 条边组成的有向图 $G$。第 $i$ 条边从 $u_i$ 指向 $v_i$。

图 $G$ 的一条欧拉路径是满足以下条件的顶点序列 $(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$，表示测试数据组数。

接下来描述 $T$ 组测试数据。每组测试数据的格式如下：

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

其中，给定一个由 $N$ 个顶点和 $M$ 条边组成的有向图，第 $i$ 条边从 $u_i$ 指向 $v_i$。

【输出】

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

Yes
$v_0$ $\ldots$ $v_{M}$
$e_0$ $\ldots$ $e_{M-1}$

【输入样例】

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

【输出样例】

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

【输入样例2】

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

【输出样例2】

Yes
0

Yes
0 1
0
Yes
4 4
0
No
Yes
3 6 3
0 1
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_directed

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