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$ に向けて張られています。

与えられたグラフにサイクルが含まれるならば、辺素な サイクルを 1 つ見つけて報告してください。存在しないならばその旨を報告してください。サイクルが複数含まれるならばどれを出力しても構いません。

Constraints
制約

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.

例えば $L = 2, e = (1, 4)$ も正答になります。

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

辺素なサイクル、つまり $e_i \neq e_j$ ならば正答が得られるため、$L = 6, e = (0, 1, 2, 3, 4, 5)$ も正答になります。$L = 6, e = (0, 1, 2, 0, 4, 5)$ は正答とならないことに注意してください。


Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions