无向图环检测（Cycle Detection (Undirected)）

问题描述

给你一个含 $N$ 个顶点、$M$ 条边的无向图。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。
请判断图中是否存在环；若存在，输出任意一个环。

环定义为顶点序列 $(v_0, v_1, \dots, v_{L-1})$ 与边序列 $(e_0, e_1, \dots, e_{L-1})$，满足：

• $L \ge 1$
• $i \ne j \Rightarrow v_i \ne v_j$ 且 $e_i \ne e_j$
• 对 $0 \le i < L-1$，边 $e_i$ 连接 $v_i$ 与 $v_{i+1}$
• 边 $e_{L-1}$ 连接 $v_{L-1}$ 与 $v_0$

约束条件

• $1 \leq N \leq 5 \times 10^5$
• $0 \leq M \leq 5 \times 10^5$
• $0 \leq u_i, v_i < N$

输入格式

$N\ M$
$u_0\ v_0$
$u_1\ v_1$
:
$u_{M-1}\ v_{M-1}$

输出格式

• 若无环：

  -1

• 否则：

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

其中 $v_i$ 为环上顶点（按顺序），$e_i$ 为对应边的编号（0-based）。

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

4
3 1 2 0
3 4 0 1

10 1
3 3

1
3
0

10 3
3 5
3 5
5 3

2
5 3
0 1

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

-1

6 0

-1