Mezclando Árboles

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 128M

Author:

Problem types

Allowed languages

Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Nikita, estudiante de traslado que sucede ser la más hermosa de su preuniversitario, está haciendo un grafo como regalo de cumpleaños para su novio, un aprendiz de programador!! Ella a dibujado un grafo no dirigido y conexo de $n$ ~n~ nodos numerados del $1$ ~1~ al $n$ ~n~ en su cuaderno.

Nikita ha dibujado los nodos usando los colores blanco y negro, pintando cada nodo completamente de un color. Siendo $n_{B}$ ~n_{B}~ el número de nodos blanco y $n_{N}$ ~n_{N}~ el número de nodos negros, has sabido que el grafo fue hecho de forma tal que no hay dos nodos adyacentes con la misma coloración y que el valor $D = abs(n_{B} - n_{N})$ ~D = abs(n_{B} - n_{N})~ es el menor posible puesto que Nikita está buscando el mejor atractivo en su pintura.

Sin embargo, el mundo no es color rosa y el pequeño hermano travieso de Nikita ha borrado algunas de las aristas y todos los coloreamientos del grafo!! Como resultado del comportamiento de su hermanito, el grafo se ha descompuesto en una o más componentes conexas. Viendo a Nikita tan desconsolada mientras contemplas su regalo hecho añicos has decidido ayudarla a reconstruir el grafo añadiendo $K$ ~K~ aristas logrando que las propiedades del obsequio inicial se cumplan en el nuevo.

En una situación normal dado el grafo descompuesto, tendrías que construir y colorear un grafo conexo a partir del mencionado consiguiendo que la diferencia $abs(n_{B} - n_{N})$ ~abs(n_{B} - n_{N})~ entre nodos coloreados sea lo menor posible. Pero, dada la naturaleza de tu relación con Nikita, solo necesitas decirle como confirmación de proeza realizada el valor de $D$ ~D~.

Entrada

La primera línea contiene respectivamente dos enteros separados por espacio $n$ ~n~ (el número de nodos en el grafo original, $1 \leq n \leq 2 \times 10^5$ ~1 \leq n \leq 2 \times 10^5~) y $m$ ~m~ (el número de aristas en el grafo descompuesto, $0 \leq m \leq \min(5 \times 10^5, \frac{n \times (n - 1)}{2})$ ).

Cada una de las $m$ ~m~ líneas siguientes contiene dos enteros separados por espacio, $u$ ~u~ y $v$ ~v~, que describen una arista bidireccional entre los nodos $u$ ~u~ y $v$ ~v~ en el grafo descompuesto. Se garantiza que cada arista se encuentra entre dos nodos distintos y que no habrá más de una arista entre cualesquiera dos nodos.

Salida

La salida consta de una sola línea con el número deseado.

Ejemplos

Entrada 1

2 1
1 2

Salida 1

Entrada 2

Salida 2

Comments

0

jcg commented on Jan. 25, 2018, 7:29 p.m.

porque si ya acepte el problema me sale como que lo tengo intentado, pero no resuelto??

0

josed commented on Jan. 25, 2018, 9:28 p.m.

Ya debe haberte salido bien. Estaba demorando un poquito en actualizarse, seguiremos revisando...