Областная олимпиада по математике, 2008 год, 9 класс

В стране 100 дорог (каждая дорога соединяет ровно два города и на дорогах двустороннее движение). Известно, что из любых трех дорог можно выбрать две, которые не выходят из одного города. Докажите, что найдутся 40 дорог, никакие две из которых не выходят из одного города.