11262: [yosupo] Graph - Eulerian Trail (Undirected)
[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 vertex $u_i$ and $v_i$. This graph may not be simple.
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$ connects $v_i$ and $v_{i+1}$.
Determine if an eulerian trail of $G$ exists, and output if it exists.
You are given an undirected graph $G$, consisting of $N$ vertices and $M$ edges. The $i$-th edge connects vertex $u_i$ and $v_i$. This graph may not be simple.
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$ connects $v_i$ and $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 \leq2\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 \leq2\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
0 2
0 2
0 3
1 3
2 3
3 3
4 6
0 1
0 2
0 3
1 2
1 3
2 3
6 10
0 3
1 2
4 0
5 1
4 4
2 3
1 3
3 2
1 4
5 1
Sample 1 Output
Yes
2 0 1 3 0 2 3 3
2 0 4 3 1 5 6
No
Yes
1 2 3 0 4 4 1 5 1 3 2
1 7 0 2 4 8 9 3 6 5
Sample 2 Input
4
10 0
10 1
0 1
10 1
4 4
10 2
4 4
5 5
Sample 2 Output
Yes
0
Yes
0 1
0
Yes
4 4
0
No