有向图环检测（Cycle Detection (Directed)）

问题描述

给你一个含 $N$ 个顶点、$M$ 条边的有向图。第 $i$ 条边从顶点 $u_i$ 指向顶点 $v_i$。
请找出一个边不相交的环（edge-disjoint cycle），并输出该环；若不存在任何环，输出 -1（要换行）。

注：题目要求“edge-disjoint cycle”但仅需输出一个环，且说明“若有多个，任选其一”，因此此处“edge-disjoint”应理解为单个环内部边互不重复（即简单环），而非多个环之间边不相交。标准解释为：输出任意一个简单有向环即可。

约束条件

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

输入格式

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

输出格式

• 若无环：

  -1

• 否则：

  $L$
  $e_0$
  $e_1$
  :
  $e_{L-1}$

其中：

• $L$ 是环中边的数量；
• $e_i$ 是环中第 $i$ 条边的编号（$0$-based），满足 $e_0, e_1, \dots, e_{L-1}$ 构成一个有向环（即 $v_{e_i} = u_{e_{i+1}}$，下标模 $L$）。

5 7
0 3
0 4
4 2
4 3
4 0
2 1
1 0

4
1
2
5
6

For instance, $L=2$, $e=(1,4)$ is also a valid answer.

2 1
1 0

-1

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

3
0
1
2

Any edge-disjoint cycles (so it satisfies the rule: $e_i \ne e_j$) can get accepted, so $L=6$, $e=(0,1,2,3,4,5)$ is also a valid answer. Note that $L=6$, $e=(0,1,2,0,4,5)$ is not a valid answer.