Знаменитый скульптор Кикассо отправляется в мировое турне!

Ну, не такое уж оно на самом деле и мировое. Но ведь возможность своими глазами повидать работы скульптора и не должна быть у всех, правда? Иначе в этом не было бы никакой эксклюзивности. Поэтому своё мировое турне Кикассо проведёт целиком и полностью в своей родной стране — Берляндии.

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

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

Обратите внимание, промежуточные маршруты могут проходить через города, которые назначены для турне, а также проходить через один и тот же город дважды. Например, турне может выглядеть так: . Надчёркиваниями обозначены четыре города, в порядке их посещения: [1, 5, 2, 4].

Отметим, что Берляндия — высокотехнологичная страна, поэтому с помощью нанотехнологий все дороги были переделаны таким образом, что они имеют одинаковую длину. По этой же причине перемещение на обычных автомобилях в ней не очень популярно и может случиться, что существуют такие пары городов, что из одного из них вообще нельзя добраться на автомобиле до другого. Однако, Кикассо весьма консервативен и использует исключительно автомобильный транспорт в своём турне, поэтому вам нужно выбрать города таким образом, чтобы турне могло состояться, то есть, чтобы скульптор мог провести его, используя только автомобиль. Гарантируется, что это всегда можно сделать.