사이클 검출 (무방향)

$N$개의 정점과 $M$개의 간선으로 이루어진 무방향 그래프가 주어진다. $i$번째 간선은 정점 $u_i$와 $v_i$를 연결한다. 이 그래프는 단순 그래프가 아닐 수도 있다.

사이클은 다음 조건을 만족하는 정점의 수열 $(v_0, \ldots, v_{L-1})$와 간선의 수열 $(e_0, \ldots, e_{L-1})$의 쌍이다.

• $L\geq 1$
• $i\neq j \implies v_i\neq v_j, e_i\neq e_j$
• $0\leq i < L- 1$에 대해, 간선 $e_i$은 $v_i$와 $v_{i+1}$를 연결한다
• 간선 $e_{L-1}$은 $v_{L-1}$와 $v_{0}$를 연결한다

$G$에 사이클이 존재하는지 판별하고, 존재한다면 출력한다. 사이클이 여러 개라면 그중 아무거나 출력한다.

제한 조건

• $1 \leq N \leq 500000$
• $0 \leq M \leq 500000$
• $0 \leq u_i \lt N$
• $0 \leq v_i \lt N$

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

사이클이 없다면 -1을 출력한다. 그렇지 않다면 사이클 하나를 다음 형식으로 출력한다.

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