BG-MO 2018 Problem 6

On a planet there are $M$ countries and $N$ cities. There are two-way roads between some of the cities. It is given that:

(1) In each county there are at least three cities;

(2) For each country and each city in the country is connected by roads with at least half of the other cities in the countries;

(3) Each city is connceted with exactly one other city ,that is not in its country;

(4) There are at most two roads between cities from cities in two different countries;

(5) If two countries contain less than $2M$ cities in total then there is a road between them.

Prove that there is cycle of lenght at least $M+\frac{N}{2}$ .