Las ~N~ vacas del granjero John están numeradas del ~1~ al ~N~. Las relaciones de amistad entre las vacas se pueden modelar como un grafo no dirigido con ~M~ aristas. Dos vacas son amigas si y solo si existe una arista entre ellas en el grafo.

En una sola operación, puedes añadir o eliminar una arista del grafo. Calcula el número mínimo de operaciones necesarias para asegurar que se cumpla la siguiente propiedad: Si las vacas ~a~ y ~b~ son amigas, entonces para cada vaca ~c~, al menos una de ellas, ~a~ o ~b~, es amiga de ~c~.

Entrada

La primera línea contiene ~N~ y ~M~.

Las siguientes ~M~ líneas contienen cada una un par de amigas, ~a~ y ~b~. Ningún par de amigas aparece más de una vez.

Salida

Número de aristas que se deben agregar o eliminar.

Restricciones

• ~2 \leq N \leq 16~
• ~0 \leq M \leq N(N - 1)/2~
• ~1 \leq a < b \leq N~

Ejemplo #1 de Entrada

3 1
1 2

Ejemplo #1 de Salida

1

La red incumple la propiedad. Podemos agregar una de las aristas ~(2,3)~ o ~(1,3)~, o eliminar la arista ~(1,2)~ para solucionarlo.

Ejemplo #2 de Entrada

3 2
1 2
2 3

Ejemplo #2 de Salida

0

No es necesario realizar cambios.

Ejemplo #3 de Entrada

4 4
1 2
1 3
1 4
2 3

Ejemplo #3 de Salida

1

USACO 2025 February Contest, Gold Problem 3. Friendship Editing.