Matcom Online Grader

En la Facultad de Matemática y Computación de la Universidad de La Habana todos los estudiantes son muy buenos amigos, tanto es así que no importa cuál trío usted escoja, siempre al menos dos son amigos. Además, para cualquier par de estudiantes existe siempre una cadena de amistad que los une. Más formalmente, una cadena de amistad es una secuencia $a_1, a_2,…, a_k$ de estudiantes tal que ai es amigo de $a_{i-1}$ $(1 \leq i \lt k)$. Se dice que la secuencia $a_1, a_2,…, a_k$ tiene longitud $k$. Conociendo todos los pares de amigos de la facultad, se desea determinar la cadena de amistad de longitud máxima.

La primera línea contiene dos enteros $N$ y $M$ separados por espacio, la cantidad de estudiantes de la Facultad de Matemática y Computación, y la cantidad de pares de amigos $(1 \leq N \leq 1000, 1 \leq M \leq 499500)$. Los estudiantes estarán identificados convenientemente con los enteros $1, 2, ..., N$. Las siguientes $M$ líneas describen cada una de las parejas de amigos de MATCOM. Cada pareja de amigos se representa con dos enteros diferentes $a$ y $b$ separados por espacio $(1 \leq a, b \leq N)$. No hay pareja de amigos repetidos en la entrada.

La cadena de amistad de longitud máxima de la facultad representada con $K$ enteros $a_1, a_2, ..., a_k$ $(1 \leq K \leq N)$ donde $a_i$ es el identificador de un estudiante de la facultad. Note que en la salida no deben aparecer estudiantes repetidos y cada par de estudiantes consecutivos en la secuencia deben ser amigos .