1. (10 points) In country $B$, there are 4 southern cities and 5 northern cities. Transportation links connect each southern city with each northern city in both directions; there is no transportation link between other pairs of cities. A traveler starts from a certain southern city, plans to visit all southern cities once and return to the starting point. How many different route options for such a journey exist?

a) $4!\times 5$ !;

b) $3!\times 5^{4}$;

c) $4^{4} \times 4$ !;

d) $3^{4} \times 5$ !;

e) another answer.
Answer: b).

Solution. Since there is no direct transportation between the southern cities, when moving from one southern city to another southern city, a transfer will have to be made in some northern city. The number of ways to visit the remaining southern cities is $(4-1)!$; the number of ways to choose a northern city for one transfer is 5. To return to the original southern city, 4 transfers in northern cities are required. From this, we get the answer.