Are you sure about the problem condition??? I claim the answer is $n=1$. Example that there cannot be only two airline: Let we have two cities Burgas and Sofia and the rest of the country to be $G$. If there is only one flight from Burgas to $G$ with company $1$ and only one flight from Sofia to $G$ to be with company $2$, as Burgas and Sofia don't have a common neighbor. Then the problem conditions are met (the distance between Sofia and Burgas is at least $3$), but there is no way Burgas -> Sofia using only one company. Here we used that $2018\le\binom{98}{2}+1$ so that we can fill $G$ and color it randomly.

Yeah, I checked the original formulation and I think I have translated it correctly, no idea if there has been a correction during the contest and there is no official solution available either.

Hm, what if the formulation meant "find the largest $n$ for which there exists a graph and a colouring such that for any two vertices..." rather than "find the largest $n$ for which for all graphs and colouring it is the case that for any two vertices..."

Ok, the correct formulation indeed is "maximal $n$ for which there exists $G$ with $100$ vertices, $2018$ edges and diameter at least $3$ and a colouring of the edges of $G$ in $n$ colours such that between any two vertices there is a monochromatic path". This is combined Lemma 2.1 with Theorem 6 in Colorful monochromatic connectivity by Caro and Yuster, appears in August 2011 Discrete Mathematics 311(16):1786-1792. To me, the approach seems unnatural to think of, does anyone have a better approach? At least the example part is easy, though it is funny that it holds for any connected graph rather than a concrete one. (The existence of required monochromatic paths requires in particular the graph to be connected.) For a connected graph on $v = 100$ vertices and $e = 2018$ edges one can take a spanning tree and colour its $v-1$ edges in one colour and all other $e-v+1$ edges in a different colour each, for a total of $e-v+2 = 1920$ colours. More colours are not possible for graphs for which some two vertices are at distance $3$ or larger, from what the above paper shows.