Question 194
There are $3,999,999$ cities in Antarctica, and some pairs of them are connected by roads. It is known that, given any two cities, there is a sequence of roads leading from one to the other. Prove that the cities can be divided into $1999$ groups (of $2001$ cities each) such that, given any two cities in the same group, it is possible to get from one to the other using at most $4000$ roads.