无向图找环

【题目描述】

给定一个无向图 $G$，它由 $N$ 个顶点和 $M$ 条边组成。 第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。 该图不一定是简单图。

一个环是由顶点序列 $(v_0, \ldots, v_{L-1})$ 和边序列 $(e_0, \ldots, e_{L-1})$ 构成的二元组，并满足以下条件：

• $L\geq 1$
• $i\neq j \implies v_i\neq v_j, e_i\neq e_j$
• 对于 $0\leq i < L- 1$，边 $e_i$ 连接 $v_i$ 和 $v_{i+1}$
• 边 $e_{L-1}$ 连接 $v_{L-1}$ 和 $v_{0}$

判断 $G$ 中是否存在环，如果存在则输出一个环。 如果存在多个环，输出任意一个即可。

【输入】

$N$ $M$
$u_0$ $v_0$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{M-1}$ $v_{M-1}$

【输出】

如果不存在环，输出 -1。否则按照以下格式输出其中一个环。

$L$
$v_0$ $v_1$ $\ldots$ $v_{L-1}$
$e_0$ $e_1$ $\ldots$ $e_{L-1}$

【输入样例】

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

【输出样例】

4
3 1 2 0
3 4 0 1

【输入样例2】

10 1
3 3

【输出样例2】

1
3
0

【输入样例3】

10 3
3 5
3 5
5 3

【输出样例3】

2
5 3
0 1

【输入样例4】

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

【输出样例4】

-1

【输入样例5】

6 0

【输出样例5】

-1

【数据范围】

• $1 \leq N \leq 500000$
• $0 \leq M \leq 500000$
• $0 \leq u_i \lt N$
• $0 \leq v_i \lt N$

【来源】

Library Checker（yosupo06） cycle_detection_undirected

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