6. En un planeta hay $M$ países y $N$ ciudades. Entre algunas de las ciudades hay carreteras de doble sentido. Se sabe que: (1) En cada país hay al menos tres ciudades; (2) Para cada país y cada ciudad del país, esta está conectada por carreteras con al menos la mitad de las demás ciudades del país; (3) Cada ciudad está conectada con exactamente una otra ciudad que no está en su país; (4) Hay a lo sumo dos carreteras entre ciudades de dos países distintos; (5) Si dos países contienen en total menos de $2M$ ciudades, entonces hay una carretera entre ellos. Demuestra que existe un ciclo de longitud al menos $M+\frac{N}{2}$.