st 编号

【题目描述】

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

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

再给定 $G$ 的两个顶点 $s$ 和 $t$。

判断是否存在顶点的一个排列 $p = (p_0,\ldots,p_{N-1})$ 满足下面的条件，若存在则求出这样一个排列。

• 对每条边，若 $p_{u_i} < p_{v_i}$ 则把这条边从 $u_i$ 定向到 $v_i$，若 $p_{v_i} < p_{u_i}$ 则从 $v_i$ 定向到 $u_i$。则对于任意顶点 $v$，都存在一条从 $s$ 到 $t$ 且经过 $v$ 的路径。

【输入】

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

【输出】

若不存在满足条件的排列 $p$，输出 No。否则按如下格式输出一个排列 $p$：

Yes
$p_0$ $\ldots$ $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

【输入样例2】

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

【输出样例2】

No
Yes
0 1
No

【数据范围】

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

【来源】

Library Checker（yosupo06） st_numbering

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