There are $2000$ cities in the country, some pairs of cities are connected by roads. It is known that no more than $N$ different non-self-intersecting cyclic routes of odd length. Prove that the country can be divided into $2N +2$ republics so that no two cities from the same republic are connected by a road.