st-编号（st-Numbering）

问题描述

本题有 $T$ 组测试数据。
对每组，给定一个无向图 $G$（含 $N$ 个顶点、$M$ 条边，无自环，但可能含重边），以及两个不同顶点 $s$ 和 $t$。

判断是否存在一个顶点排列 $p = (p_0, p_1, \dots, p_{N-1})$，满足：

• 对每条边 $(u_i, v_i)$，若 $p_{u_i} < p_{v_i}$，则定向为 $u_i \to v_i$；否则定向为 $v_i \to u_i$；
• 在该定向下，对任意顶点 $v$，存在一条从 $s$ 到 $t$ 的路径经过 $v$。

若存在，输出任意一个满足条件的排列 $p$；否则输出 No。

约束条件

• $1 \leq T \leq 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $0 \leq s, t < N$
• $s \ne t$
• $0 \leq u_i, v_i < N$
• $u_i \ne v_i$
• 所有测试用例中 $\sum N \leq 2 \times 10^5$，$\sum M \leq 2 \times 10^5$

输入

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

输出

若不存在满足条件的排列，输出一行：

No

否则输出：

Yes
$p_0\ p_1\ \cdots\ p_{N-1}$

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

Yes
2 0 1
Yes
1 0 2 3
No
Yes
1 3 0 4 2

3
2 0 0 1
2 2 0 1
0 1
1 0
3 2 0 1
0 1
1 0

No
Yes
0 1
No