№ 13816

В стране 100 городов. Между любыми двумя городами либо нет соединения, либо налажено авиасообщение, либо есть железная дорога (одновременно и авиасообщения, и железной дороги быть не может). Известно, что если два города соединены с третьим железной дорогой, то между ними есть авиалиния, а если два города соединены с третьим авиалиниями, то между ними есть железная дорога. Из-за стихийного бедствия отменили все авиарейсы в стране. Правительство постановило в некоторых городах разместить центры гуманитарной помощи, причём так, чтобы из каждого города можно было добраться в подобный центр. Докажите, что необходимо открыть хотя бы 20 таких центров.