11263: [yosupo] Graph - st-Numbering
[Creator : ]
Description
This problem has $T$ cases.
You are given an undirected graph $G$, consisting of $N$ vertices and $M$ edges. The $i$-th edge connects vertices $u _ i$ and $v _ i$. This graph may not be simple but does not contain any self-loops.
You are also given two vertices $s$ and $t$ of $G$.
Determine if there exists a permutation $p = (p _ 0,\ldots,p _ {N - 1})$ of the vertices satisfying the following condition, and if so, find such a permutation.
- Orient each edge of $G$ from $u _ i$ to $v _ i$ if $p _ {u _ i} < p _ {v _ i}$, or from $v _ i$ to $u _ i$ if $p _ {v _ i} < p _ {u _ i}$. Then, for any vertex $v$, there exists a path from $s$ to $t$ that passes through $v$.
You are given an undirected graph $G$, consisting of $N$ vertices and $M$ edges. The $i$-th edge connects vertices $u _ i$ and $v _ i$. This graph may not be simple but does not contain any self-loops.
You are also given two vertices $s$ and $t$ of $G$.
Determine if there exists a permutation $p = (p _ 0,\ldots,p _ {N - 1})$ of the vertices satisfying the following condition, and if so, find such a permutation.
- Orient each edge of $G$ from $u _ i$ to $v _ i$ if $p _ {u _ i} < p _ {v _ i}$, or from $v _ i$ to $u _ i$ if $p _ {v _ i} < p _ {u _ i}$. Then, for any vertex $v$, there exists a path from $s$ to $t$ that passes through $v$.
Input
$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$
$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$
Output
If there exists no permutation $p$ satisfying the condition, print `No`. Otherwise, print a permutation $p$ in the following format.
Yes
$p _ 0$ $\ldots$ $p _ {N - 1}$
Yes
$p _ 0$ $\ldots$ $p _ {N - 1}$
Constraints
- $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 \lt N$
- $s\neq t$
- $0 \leq u _ i, v _ i \lt N$
- $u _ i\neq v _ i$
- The sum of $N$ over all test cases does not exceed $2\times 10^5$.
- The sum of $M$ over all test cases does not exceed $2\times 10^5$.
- $1 \leq N \leq 2\times 10^5$
- $0 \leq M \leq 2\times 10^5$
- $0 \leq s, t \lt N$
- $s\neq t$
- $0 \leq u _ i, v _ i \lt N$
- $u _ i\neq v _ i$
- The sum of $N$ over all test cases does not exceed $2\times 10^5$.
- The sum of $M$ over all test cases does not exceed $2\times 10^5$.
Sample 1 Input
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
Sample 1 Output
Yes
2 0 1
Yes
1 0 2 3
No
Yes
1 3 0 4 2
Sample 2 Input
3
2 0 0 1
2 2 0 1
0 1
1 0
3 2 0 1
0 1
1 0
Sample 2 Output
No
Yes
0 1
No