Los puentes de Enelogonia P51971

El país de Enelogonia está formado por $n$ islas unidas por $m$ puentes bidireccionales, de manera que desde cualquier isla se puede llegar a todas las otras a través de los puentes. Las leyes de Enelogonia prohiben que haya dos o más puentes uniendo las mismas islas, o puentes entre una isla y sí misma.

El gobierno quiere organizar un desfile que pase por todos los puentes exactamente una vez, y que empiece y termine en la capital, que es una isla desconocida para nosotros. El gobierno se ha dado cuenta de que con los puentes que hay actualmente quizá no sea posible organizar tal desfile, por lo que permite construir hasta $k$ puentes nuevos. Vuestra tarea es decidir qué puentes construir para asegurar que el desfile sea posible.

Entrada

La entrada empieza con $n$, $m$ y $k$. Siguen $m$ pares $x$ $y$ que indican que las islas $x$ e $y$ estan unidas por un puente. Podéis asumir $4 \le n \le 500$, $k \ge n - 1$, y $m + k \le n(n - 1)/2$. Las islas se numeran a partir de 0.

Salida

En la primera línea, escribid el número $p$ de puentes que se van a crear, entre 0 y $k$. Las siguientes $p$ líneas deben contener dos enteros $x$ e $y$ separados por un espacio, indicando entre qué islas se va a crear un puente. Si existe más de una solución, escribid cualquiera de ellas. Si no hay solución posible con $k$ o menos puentes, la salida tiene que ser una sola linea con un -1. Seguid exactamente el formato indicado.

Puntuación

• test-1:   Resolver casos con $n \le 7$.

• test-2:   Resolver casos con $n$ impar y $m+k = n(n - 1)/2$.

• test-3:   Resolver todo tipo de casos.