Командная олимпиада, о которой идёт речь в этой задаче, проходила по правилам, похожим на правила олимпиады, в которой вы сейчас участвуете. Отличие было только в одном: при ранжировании команд не учитывается штрафное время. При этом в случае равного количества решённых задач выше в таблице располагается та команда, чьё имя следует раньше в лексикографическом порядке.

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

Спортивный программист для достижения вершин своего мастерства должен быть натренирован в совершенно разных аспектах, в том числе и физически. Кто-то для этого садится на велосипед, кто-то ныряет в бассейн, а молодой программист Влад бегает по стадиону. Но из-за неаккуратного обращения с личными вещами его секундомер может измерять время только в минутах, без указания секунд и тем более их долей. Причём, если секундомер показывает, например, 1, то это может обозначать и время ровно 2 минуты, так как 1.(9) = 2.

Чтобы следить за прогрессом своего ученика, тренеру Влада приходится довольствоваться показаниями этого прибора. Каждый раз, когда Влад пробегает мимо тренера, сделав очередной круг по стадиону, тот записывает в блокнот показания секундомера в минутах. Первый раз тренер записывает время в момент, когда Влад пробежал первый круг. Фактически показания секундомера соответствуют целому числу минут, прошедших к определенному моменту времени.

На контрольной тренировке Влад бегал с постоянной скоростью, однако по записям тренера не так легко сказать, с какой именно. Напишите программу, которая поможет тренеру определить за какое минимальное, а также максимальное возможное время Влад мог пробегать каждый круг. Известно, что Влад начал бегать в момент времени 0 в том месте, где стоит тренер.

Как вы помните, Джонни работает в министерстве финансов одной небольшой страны. По роду службы ему приходится инспектировать отечественные авиакомпании и изучать маршруты, которые те предлагают.

В стране есть n городов. По государственным законам авиакомпания должна предоставлять услуги двустороннего перелёта между некоторыми парами городов, причём в целях унификации и стандартизации продолжительность любого полёта должна составлять ровно один день.

Авиакомпания называется крупной, если с помощью рейсов этой компании можно добраться из любого города страны до любого другого. Крупная авиакомпания называется экономной, если при этом количество маршрутов, ею предлагаемое, минимально возможное, которое может быть у крупной компании.

Государственная антимонопольная служба возбудила расследование против крупной авиакомпании «Aero-float». Ей предъявлено обвинение в излишней неэкономности. Джонни было поручено проинспектировать «Aero-float» в целях обнаружения финансовых махинаций, но авиакомпания отказалась раскрывать полный список предоставляемых ею прямых рейсов. После продолжительных переговоров руководство компании согласилось сообщить Джонни информацию о минимально возможном количестве перелётов между каждой парой городов, если использовать только прямые рейсы «Aero-float».

Используя эту информацию, помогите Джонни установить, может ли компания «Aero-float» быть экономной или нет? Более формально, установите, существует ли набор рейсов, при котором число рейсов в кратчайших маршрутах именно такие, как было сообщено Джонни, и при котором компания является экономной?