Let $G$ be the set of all cities in the country. We call a pair $(A, Z)$, where $A$ and $Z$ are disjoint subsets of $G$ good if all cities in the set $A$ can be visited using only bus such that no city is visited twice and all cities in the set $Z$ can be visited using only train such that no city is visited twice.

Let $(A, Z)$ be a good pair such that the set $A \cup Z$ has the maximal number of elements. If we prove $A \cup Z = G$, the statement of the problem holds.

Let us assume the opposite, i.e. there is a city $g$ which isn't from $A$ nor $Z$. Without loss of generality we can assume that $A$ and $Z$ are non-empty, because otherwise we can transfer any city from a non-empty set to an empty one.

Let $n$ be the number of cities in the set $A$, and $m$ the number of cities in the set $Z$. Let us arrange the cities from $A$ in the series $a_1, \dots, a_n$ such that every two consecutive cities in that series are connected by a direct bus line. Also, let us arrange the cities from $Z$ in the series $z_1, \dots, z_m$ such that every two consecutive cities in that series are connected by a direct train line.

Since we assumed that the pair $(A, Z)$ is maximal, the cities $g$ and $a_1$ have to be connected by train (otherwise the pair $(A \cup \{g\}, Z)$ would be a good pair whose union would have more elements than $A \cup Z$), and $g$ and $z_1$ have to be connected by bus (otherwise the pair $(A, Z \cup \{g\})$ would be a good pair whose union would have more elements than $A \cup Z$).

The cities $a_1$ and $z_1$ have to be connected by bus or by train.

If $a_1$ and $z_1$ are connected by bus, let us put $A' = \{z_1, g, a_1, \dots, a_n\}$ and $Z' = \{z_2, \dots, z_m\}$. Then $(A', Z')$ is a good pair and the number of elements of $A' \cup Z'$ is greater than the number of elements of $A \cup Z$, which contradicts the assumption.

If $a_1$ and $z_1$ are connected by train, let us put $A'' = \{a_2, \dots, a_n\}$ and $Z'' = \{a_1, g, z_1, z_2, \dots, z_m\}$. Then $(A'', Z'')$ is a good pair and the number of elements of $A'' \cup Z''$ is greater than the number of elements of $A \cup Z$, which contradicts the assumption.

Since all cases lead to contradiction, we conclude that the assumption was wrong and that every city is either in the set $A$ or in the set $Z$.