Let us denote countries as $X, Y, Z, T$. We randomly choose one city $x, y, z, t$ from each country respectively. In case there are all 6 roads between them, then the statement has been proved.

In case there is quadruple that is connected via less than 5 roads, then there has to exist a quadruple that is connected via all 6 roads, otherwise, the number of possible roads is less than $\frac{5}{6}$. Therefore, in order to comply with the problem statement, each four cities have to be connected with exactly 5 roads. Same every two countries have to be connected via exactly $\frac{5}{6}$ from the total number of possible roads between those countries, hence there are unconnected cities between countries.

Choose cities $x \in X$, $y \in Y$ that are not connected. Consider arbitrary $z \in Z$ and $t \in T$. Since quadruple $x, y, z, t$ is connected with exactly 5 roads, then $z, t$ have to be connected. Since we chose arbitrary cities $z \in Z$ and $t \in T$, then every two cities of $Z$ and $T$ are connected, which yields a contradiction with connection between countries.