UA-UMO 2023 Problem 118

There are $2024$ cities in a country, every two of which are bidirectionally connected by exactly one of three modes of transportation - rail, air, or road. A tourist has arrived in this country and has the entire transportation scheme. He chooses a travel ticket for one of the modes of transportation and the city from which he starts his trip. He wants to visit as many cities as possible, but using only the ticket for the specified type of transportation. What is the largest $k$ for which the tourist will always be able to visit at least $k$ cities? During the route, he can return to the cities he has already visited.

Proposed by Bogdan Rublov