Se le proporciona un grafo simple no dirigido sin bucles ni aristas múltiples. Algunas de las aristas están marcadas como especiales (Special).

Su tarea es encontrar un ciclo simple donde, para cada arista especial, dicha arista pertenezca al ciclo o ninguno de sus extremos toque el ciclo. El ciclo no puede repetir vértices. Imprima cualquier solución, o informe si no existe ninguna.

Entrada

La primera línea de la entrada contiene tres enteros $n$ ($2 \le n \le 150$), $m$ ($1 \le m \le \frac{n(n-1)}{2}$) y $k$ ($1 \le k \le m$), donde $n$ es el número de nodos en el grafo, $m$ es el número de aristas y $k$ es el número de aristas que son especiales. Los nodos están numerados del 1 al $n$.

Cada una de las siguientes $m$ líneas contiene dos enteros $a$ y $b$ ($1 \le a < b \le n$), que denotan una arista no dirigida entre los nodos $a$ y $b$. Todas las aristas son distintas. Las primeras $k$ aristas son las aristas especiales.

Salida

Imprima un entero que indique la longitud del ciclo encontrado en una línea. En las líneas siguientes, imprima los vértices del ciclo en orden a lo largo del mismo, uno por línea. Si no existe tal ciclo, simplemente imprima $-1$.

Ejemplos

Entrada 1

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

Salida 1

8
1
4
5
6
7
8
3
2

Entrada 2

4 6 3
1 2
1 3
1 4
2 3
3 4
2 4

Salida 2

-1