Городская олимпиада по математике среди физ-мат школ Алматы, 2009 год

В стране есть $n$ городов, некоторые пары городов соединены дорогами. Известно, что если выехать из любого города, совершить путь (по дорогам) по другим городам и снова вернуться в исходный город, то в таком маршруте мы всегда посетим четное количество городов (включая исходный город). Определите наибольшее возможное количество дорог в этой стране.