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

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

Имеется бесконечное количество прямоугольных кирпичей размерами \(x_i \times y_i \times z_i\), каждый из которых можно ставить на любую грань (размеры каких-то двух стороны будут размерами основания, размер третьей стороны – высотой). Ваша задача – написать программу, находящую максимальную высоту башни, которую можно построить из этих кирпичей. Один кирпич может быть поставлен на другой, если размеры основания верхнего кирпича строго меньше соответствующих размеров основания нижнего.