VN-TST 2019 Problem 1

In a country there are $n\geq 2$ cities. Any two cities has exactly one two-way airway. The government wants to license several airlines to take charge of these airways with such following conditions:

i) Every airway can be licensed to exactly one airline. ii) By choosing one arbitrary airline, we can move from a city to any other cities, using only flights from this airline.

What is the maximum number of airlines that the government can license to satisfy all of these conditions?