有向图欧拉迹（Eulerian Trail (Directed)）

问题描述

给定 $T$ 组测试数据。对每组，输入一个含 $N$ 个顶点、$M$ 条边的有向图（边按输入顺序编号为 $0$ 到 $M-1$）。
判断该图是否存在欧拉迹（Eulerian trail）——即一条经过每条边恰好一次的路径（不要求回到起点）。

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

• 第一行：Yes
• 第二行：顶点序列 $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\}$ 的一个排列；
  • 对每个 $i$，边 $e_i$ 从 $v_i$ 指向 $v_{i+1}$。

若不存在，输出 No。

存在性条件（有向图）

图存在欧拉迹当且仅当满足以下之一：

1. 欧拉回路：所有顶点入度 = 出度，且图弱连通（忽略方向后连通）且至少有一条边；
2. 欧拉路径（非回路）：恰有一个顶点满足 $\text{outdeg} - \text{indeg} = 1$（起点），恰有一个顶点满足 $\text{indeg} - \text{outdeg} = 1$（终点），其余顶点入度 = 出度，且图弱连通且至少有一条边。

注意：孤立顶点（入出度均为 0）允许存在，但整个图必须在边诱导子图上弱连通（即所有有边的顶点构成一个弱连通分量）。

约束条件

• $1 \leq T \leq 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $1 \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
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

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

Yes
0

Yes
0 1
0
Yes
4 4
0
No
Yes
3 6 3
0 1
No