В государстве Древоландия есть \(N\) крупных городов, соединенных \(N - 1\) двухсторонними дорогами, причем из любого города можно добраться по этим дорогам до любого другого города. Экономика страны находится в зачаточном состоянии, а Владислав - один из первых бизнесменов в этой стране. В данный момент он подумывает о том, чтобы перевозить крупные партии товаров из одного города в другой.

Совсем недавно на дорогах страны появились \(M\) полицейских постов (они могут быть не на каждой дороге, и их может быть несколько на одной дороге). Все посты разбиты на \(P\) категорий, на одной дороге бывают посты только различных категорий. Полицейские очень любят переписываться с коллегами своей категории, а электронной почты в стране еще не существует, поэтому для передачи писем они используют проезжающих. Проезжая пост категории \(i\) без письма для полицейских этой категории, Владислав обязательно берет на посту письмо. Проезжая через очередной пост категории \(i\), Владислав обязательно отдает это письмо, причем новое письмо на этом посту он не получает. К концу поездки у Владислава не должно остаться ни одного письма.

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

Для любой дороги Владислав знает, сколько разбойников и странников находится на ней в первый год его предпринимательства, и сколько новых будут появляться каждый год (это фиксированные числа, свои для каждой дороги). Владиславу также известно расположение всех полицейских постов и категория каждого их них. Заниматься бизнесом он планирует в течение \(K\) лет.

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

Алхимики Средневековья владели знаниями о превращении различных химических веществ друг в друга. Это подтверждают и недавние исследования археологов. В ходе археологических раскопок было обнаружено m глиняных табличек, каждая из которых была покрыта непонятными на первый взгляд символами. В результате расшифровки выяснилось, что каждая из табличек описывает одну алхимическую реакцию, которую умели проводить алхимики. Результатом алхимической реакции является превращение одного вещества в другое. Заданы набор алхимических реакций, описанных на найденных глиняных табличках, исходное вещество и требуемое вещество. Необходимо выяснить, возможно ли преобразовать исходное вещество в требуемое с помощью этого набора реакций, а в случае положительного ответа на этот вопрос — найти минимальное количество реакций, необходимое для осуществления такого преобразования.

Вам дано описание дорожной сети страны. Ваша задача – найти среднюю длину кратчайшего пути между двумя городами. Средней длиной называется отношение суммы по всем парам городов (\(a\), \(b\)) длин кратчайших путей \(l_{a,b}\) из города \(a\) в город \(b\) к числу таких пар. Здесь \(a\) и \(b\) – различные натуральные числа в диапазоне от 1 до \(N\), где \(N\) – общее число городов в стране. Следует учитывать только такие пары городов, между которыми есть кратчайший путь.