11261: [yosupo] Graph - Eulerian Trail (Directed)
[Creator : ]
Description
This problem has $T$ cases.
You are given a directed graph $G$, consisting of $N$ vertices and $M$ edges. The $i$-th edge is directed from $u_i$ to $v_i$.
An eulerian trail of $G$ is a pair of sequence of vertices $(v_0,\ldots,v_M)$ and sequence of edges $(e_0,\ldots,e_{M-1})$ satisfying following conditions.
- $(e_0,\ldots,e_{M-1})$ is a permutation of $(0, \ldots, M-1)$.
- For $0\leq i < M-1$, the edge $e_i$ is directed from $v_i$ to $v_{i+1}$.
Determine if an eulerian trail of $G$ exists, and output if it exists.
You are given a directed graph $G$, consisting of $N$ vertices and $M$ edges. The $i$-th edge is directed from $u_i$ to $v_i$.
An eulerian trail of $G$ is a pair of sequence of vertices $(v_0,\ldots,v_M)$ and sequence of edges $(e_0,\ldots,e_{M-1})$ satisfying following conditions.
- $(e_0,\ldots,e_{M-1})$ is a permutation of $(0, \ldots, M-1)$.
- For $0\leq i < M-1$, the edge $e_i$ is directed from $v_i$ to $v_{i+1}$.
Determine if an eulerian trail of $G$ exists, and output if it exists.
Input
$T$
$N$ $M$
$u_0$ $v_0$
$\vdots$
$u_{M-1}$ $v_{M-1}$
$N$ $M$
$u_0$ $v_0$
$\vdots$
$u_{M-1}$ $v_{M-1}$
$\vdots$
$N$ $M$
$u_0$ $v_0$
$\vdots$
$u_{M-1}$ $v_{M-1}$
$N$ $M$
$u_0$ $v_0$
$\vdots$
$u_{M-1}$ $v_{M-1}$
$\vdots$
Output
If there exists no eulerian trail, print `No`. Otherwise, print an eulerian trail in the following format.
Yes
$v_0$ $\ldots$ $v_{M}$
$e_0$ $\ldots$ $e_{M-1}$
Yes
$v_0$ $\ldots$ $v_{M}$
$e_0$ $\ldots$ $e_{M-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 u_i, v_i \lt N$
- 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 u_i, v_i \lt N$
- 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
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
Sample 1 Output
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
Sample 2 Input
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
Sample 2 Output
Yes
0
Yes
0 1
0
Yes
4 4
0
No
Yes
3 6 3
0 1
No