Транспортная сеть страны состоит из 777 дорог, которые соединяют между собой города. Министерство транспорта решило отремонтировать все дороги, распределив между строительными компаниями города так, что каждая компания обязана отремонтировать половины всех дорог, ведущих из закреплённого за компанией города, но при этом никакая компания не должна ремонтировать всю дорогу целиком, чтобы потом сверить качество работ на стыке отремонтированных разными компаниями половин дороги. Какое наименьшее количество строительных компаний можно привлечь к ремонту, чтобы гарантированно выполнить требуемые условия?