8202: [yosupo] Graph - Cycle Detection (Directed)
[Creator : ]
Description
You are given a graph, consisting of N vertices and M edges.
The i-th edge is directed from vertex $u_i$ to vertex $v_i$.
Find and report an edge-disjoint cycle in given graph, or report that no such cycle exists.
If there are multiple cycles, print any of them.
The i-th edge is directed from vertex $u_i$ to vertex $v_i$.
Find and report an edge-disjoint cycle in given graph, or report that no such cycle exists.
If there are multiple cycles, print any of them.
Input
$N\ M$
$u_1\ v_1$
$⋮$
$u_M\ v_M$
$u_1\ v_1$
$⋮$
$u_M\ v_M$
Output
If there are no cycles, output -1.
Otherwise, output one of the cycles in the following format. $e_i$ denotes the ID of i-th edge to use. Note that $(e_0,e_1,…,e_{L−1})$ must be a cycle, and $e_i$ must not be equal to $e_j$ if $i≠j$.
$L$
$e_0$
$e_1$
$⋮$
$e_{L−1}$
Otherwise, output one of the cycles in the following format. $e_i$ denotes the ID of i-th edge to use. Note that $(e_0,e_1,…,e_{L−1})$ must be a cycle, and $e_i$ must not be equal to $e_j$ if $i≠j$.
$L$
$e_0$
$e_1$
$⋮$
$e_{L−1}$
Constraints
$2≤N≤500,000$
$1≤M≤500,000$
$0≤u_i<N$
$0≤v_i<N$
$u_i\neq v_i$
$1≤M≤500,000$
$0≤u_i<N$
$0≤v_i<N$
$u_i\neq v_i$
Sample 1 Input
5 7
0 3
0 4
4 2
4 3
4 0
2 1
1 0
Sample 1 Output
4
1
2
5
6
For instance, L=2,e=(1,4) is also a valid answer.
Sample 2 Input
2 1
1 0
Sample 2 Output
-1
Sample 3 Input
4 6
0 1
1 2
2 0
0 1
1 3
3 0
Sample 3 Output
3
0
1
2
Any edge-disjoint cycles (so it satisfies the rule: $e_i\neq 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.
Note that L=6,e=(0,1,2,0,4,5) is not a valid answer.
HINT
相同题目：Yosupo.jp。