Володя — мастер искажений. Он обладает уникальной способностью — строить портальчики! Имея два местоположения в пространстве, Володя может построить портальчик, позволяющий перемещаться между ними в любом из двух направлений. К сожалению, такое действие не обходится Володе даром, и при каждом строительстве редеет на несколько волос его и так, скажем откровенно, не очень-то густая шевелюра.

Из-за своих экстраординарных способностей, Володя привлек внимание военных. Ему поручено особо важное задание. Но обо всем по порядку.

Военная база представляет собой несколько подземных объектов, некоторые из которых соединены между собой двусторонними тоннелями, причем так, что между любыми двумя объектами есть путь по тоннелям. Ровно два объекта имеют выходы на поверхность. Для охраны тоннелей действует патрульный, который каждый день спускается в любой из объектов, имеющих выход, обходит все тоннели и выходит на поверхность через любой из объектов, имеющих выход. Он может входить и выходить через один и тот же объект, а может через разные. Руководство военной базы заметило, что патрульный проходит через некоторые тоннели по несколько раз, и решило оптимизировать схему патрулирования. Перед военными встала задача: построить систему портальчиков между объектами так, чтобы патрульный мог совершать свой обход, проходя по каждому тоннелю ровно один раз. При этом через портальчики патрульный может проходить неограниченное число раз.

Здесь-то и вступает в дело Володя: планирование и постройку системы порталов решили поручить именно ему. К несчастью для Володи, из-за строгой секретности ему не сообщили расположения тоннелей, но потребовали, чтобы система порталов выполняла задачу в любом случае. Тем не менее, некоторой информацией Володя располагает: ему известно, между какими парами объектов он может построить порталы и во сколько волос они обойдутся. Более того, завтра Володе обещают сообщить, какие два объекта имеют выходы на поверхность. Конечно же, Володя решил не терять времени и посчитать минимальные стоимости постройки для нескольких вероятных, по его мнению, пар объектов. Помогите ему!