Hay un grafo conexo no dirigido con \(N\) vértices y \(M\) aristas (numeradas de \(1\) a \(M\)), sin aristas múltiples ni lazos, en el que cada vértice tiene grado al menos 3.

Busca un circuito: una secuencia cerrada de aristas, cada una usada a lo más una vez (los vértices sí se pueden repetir), que pase por al menos \(3\) vértices distintos, y tal que el grafo siga siendo conexo después de quitar todas las aristas del circuito.

Entrada

La primera línea tiene dos enteros \(N\) \((4 \le N \le 2 \cdot 10^5)\) y \(M\) \((6 \le M \le 3 \cdot 10^5)\).

La \(i\)-ésima de las siguientes \(M\) líneas tiene dos enteros \(U\) y \(V\) \((1 \le U, V \le N,\ U \ne V)\): la arista \(i\) une \(U\) con \(V\).

Se garantiza que no hay aristas repetidas, que todo vértice tiene grado al menos \(3\) y que el grafo es conexo.

Salida

Si existe un circuito así, imprime dos líneas: la primera con la cantidad de aristas del circuito y la segunda con sus números en el orden en que se recorren. Si hay varios, cualquiera es aceptado. Si no existe, imprime una línea con el carácter *.

Notas

En el ejemplo, el circuito formado por las aristas \(14\), \(9\) y \(12\) recorre los vértices \(4\), \(7\) y \(8\), y al quitarlo el grafo sigue conexo. Hay otras respuestas válidas.

Ejemplo 1

Entrada

8 14
2 6
2 5
2 3
2 1
6 5
6 7
6 1
3 4
7 8
1 5
3 7
4 8
3 8
4 7

Salida

3
14 9 12

Regional Latinoamericana 2024 del ICPC, problema B («Biketopia's Cyclic Track»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.