B. La campaña de Bob
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bob es un político que recientemente ha iniciado su campaña electoral para uno de los cargos más importantes del estado. Él quiere que su campaña sea lo más efectiva posible, por lo que ha decidido contratar a un equipo de expertos en marketing político para que lo ayuden a diseñar su estrategia de campaña. El equipo de expertos ha realizado un estudio exhaustivo y ha identificado las ciudades que tienen grupos de votantes similares y ha creado un mapa que muestra las interacciones entre ellas.

Con el propósito de comunicar sus discursos políticos y propuestas, Bob ha decidido iniciar un recorrido por las diferentes ciudades del estado. En la primera semana, Bob visitará una ciudad y comunicará su discurso y propuestas. En ese momento los votantes de dicha ciudad quedarán informados sobre las mismas y comenzarán a difundir la información con las ciudades vecinas. Sin embargo, les tomará una semana completar ese proceso. En la segunda semana, dos eventos simultáneos ocurren: Bob visitará otra ciudad para continuar su campaña, y, por el estudio realizado por su equipo, se sabe que los votantes de las ciudades previamente informadas ya habrán informado a sus ciudades vecinas, por lo que estas ya podrán ser consideradas informadas. El proceso se repetirá hasta que todas las ciudades queden informadas.

Bob y su equipo tienen dos posibles estrategias para visitar las ciudades. La primera estrategia consiste en visitar las ciudades impares de manera secuencial ascendente, y la segunda estrategia consiste en visitar las ciudades pares de manera secuencial ascendente. Además, dado que visitar dichas ciudades y dar los discursos suele ser muy costoso, a Bob y su equipo les gustaría visitar la menor cantidad de ciudades posibles, y que a su vez se logre que la información del discurso llegue a todas las ciudades y a sus votantes.

Considerando las dos estrategias mencionadas, ¿Cuántas semanas le tomará a Bob comunicar su discurso político?

Imagen ilustrativa (ChatGPT).
Input

La primera línea contiene dos enteros n y m (1 ≤ n ≤ 105, ), el número de ciudades y las relaciones de vecindad entre ellas, de acuerdo con el estudio realizado por el equipo de Bob. Las siguientes m líneas contienen dos enteros u y v (1 ≤ u, v ≤ n, u ≠ v), indicando que las ciudades u y v son vecinas. Las ciudades están numeradas del 1 al n.

Output

Imprimir la cantidad mínima de semanas que le tomará a Bob comunicar su discurso político siguiendo alguna de las dos estrategias propuestas. En caso de que sea imposible que Bob pueda lograr su propósito, imprimir -1.

Examples
Input
6 6
1 4
1 2
2 3
2 5
2 4
3 6
Output
3
Input
6 6
1 4
1 2
2 3
2 4
2 5
2 6
Output
2
Input
4 2
1 3
2 4
Output
-1