Bajtysia y Bajteusz son viajeros famosos que han visitado casi todos los rincones de Bajtocja. Esta tierra consta de $n$ ciudades, numeradas del $1$ al $n$, las cuales están conectadas por una red de caminos de sentido único. Sin embargo, se han aburrido de los métodos tradicionales de viaje; ya han estado en todos los lugares a los que pueden llegar.

Recientemente, Bajtysia obtuvo un antiguo artefacto mágico: el Registro de Caminos. Este permite la creación de nuevos caminos de sentido único entre ciudades. Sin embargo, hay un inconveniente. La magia del registro es caprichosa y solo permite crear un camino entre dos ciudades si actualmente es imposible viajar desde la primera ciudad hasta la segunda utilizando la red de caminos existente (es decir, no existe una secuencia de caminos que lleve desde la primera ciudad hasta la segunda; sin embargo, puede darse el caso de que exista una secuencia de caminos que lleve desde la segunda ciudad hasta la primera). Un intento de crear un camino entre ciudades que ya están conectadas fallará y destruirá el registro.

¡Para Bajtysia y Bajteusz, este es un desafío maravilloso! Inmediatamente decidieron que quieren conjurar tantos caminos nuevos como sea posible.

Desafortunadamente, Bajtysia y Bajteusz están demasiado ocupados planeando su próxima expedición como para resolver este problema por su cuenta. Ayúdalos a planificar qué caminos deben crearse uno por uno para que su número total sea lo más grande posible.

Entrada

La primera línea de la entrada contiene dos enteros $n$ y $m$ ($1 \le n \le 1500$, $0 \le m \le n(n-1)$), que representan el número de ciudades y de caminos de sentido único en Bajtocja, respectivamente. Las siguientes $m$ líneas contienen las descripciones de los caminos. La $i$-ésima de estas líneas (para $1 \le i \le m$) contiene dos enteros $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$), indicando que hay un camino de sentido único desde la ciudad $a_i$ hasta la ciudad $b_i$. Los caminos de sentido único descritos no se repiten.

Salida

En la primera línea de la salida, imprima un único entero no negativo $k$ que represente el número máximo de caminos de sentido único que se pueden crear de tal manera que cada camino subsiguiente conecte un par de ciudades entre las cuales no sea posible viajar actualmente. Las siguientes $k$ líneas deben describir los caminos que se deben crear en orden. La $i$-ésima de estas líneas (para $1 \le i \le k$) debe contener dos enteros $c_i, d_i$ que representen las ciudades entre las cuales se debe crear el $i$-ésimo camino. En el momento de crear este camino, no debería ser posible viajar desde la ciudad $c_i$ hasta la ciudad $d_i$ utilizando los caminos ya existentes (es decir, tanto los iniciales como los creados anteriormente). Si hay múltiples soluciones posibles, imprima cualquiera de ellas.

Ejemplos

Entrada 1

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

Salida 1

3
4 1
6 4
7 6

Entrada 2

3 0

Salida 2

5
3 1
3 2
2 1
2 3
1 2

Nota

Explicación del ejemplo: En el primer ejemplo, la red de caminos existente inicialmente se ilustra a continuación.

No es posible viajar desde la ciudad 4 hasta la ciudad 1, por lo que se puede añadir dicho camino para obtener la red de caminos ilustrada a continuación.

Después de añadir caminos desde la ciudad 6 hasta la ciudad 4 y desde la ciudad 7 hasta la ciudad 6, obtenemos una red en la que es posible viajar entre cada par de ciudades. No se pueden añadir más aristas.

Subtareas

Si solo la primera línea de su respuesta es correcta, su solución recibirá el 50% de los puntos para esa prueba. No necesita imprimir las líneas subsiguientes para recibir estos puntos.