Cycle Detection

AC一覧

Problem Statement問題文

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.

$N$ 頂点 $M$ 辺の有向グラフが与えられます。$i$ 番目の辺は頂点 $u_i$ から頂点 $v_i$ に向けて張られています。

Constraints制約

• $2 \leq N \leq 500{,}000$
• $1 \leq M \leq 500{,}000$
• $0 \leq u_i \lt N$
• $0 \leq v_i \lt N$
• $u_i \neq v_i$

Input入力

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


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, \ldots, e_{L-1})$ must be a cycle, and $e_i$ must not be equal to $e_j$ if $i \neq j$.

サイクルが存在しない場合、-1 を出力してください。

そうでない場合、以下の形式で出力してください。ここで、$e_i$ は $i$ 番目に通る辺の番号を表し、$(e_0, e_1, \ldots, e_{L-1})$ は、この順に辺を通るときにサイクルを成さなければならず、$e_i \neq e_j$ $(i \neq j)$ でなければなりません。

$L$
$e_0$
$e_1$
$\vdots$
$e_{L-1}$


Sampleサンプル

# 1

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

2 1
1 0

-1


# 3

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 \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.

Timelimit: 5 secs

Before submitting, please confirm terms and conditions