В некоторой стране есть развитая сеть железных дорог. С доисторических времён и до нашего времени в стране непрерывно происходят военные перевороты, из-за которых в системе железнодорожного транспорта этой страны происходят непрерывные изменения. Дело в том, что во время очередного переворота некоторые дороги разрушаются из-за военных действий, а пока новый правитель некоторое время находится у власти, он восстанавливает часть дорог.

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

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

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

Город будущего застроен небоскребами, для передвижения между которыми и парковки транспорта многие тройки небоскребов соединены треугольной подушкой из однополярных магнитов. Каждая подушка соединяет ровно 3 небоскреба и вид сверху на нее представляет собой треугольник, с вершинами в небоскребах. Это позволяет беспрепятственно передвигаться между соответствующими небоскребами. Подушки можно делать на разных уровнях, поэтому один небоскреб может быть соединен различными подушками с парами других, причем два небоскреба могут соединять несколько подушек (как с разными третьими небоскребами, так и с одинаковым). Например, возможны две подушки на разных уровнях между небоскребами 1, 2 и 3, и, кроме того, магнитная подушка между 1, 2, 5.

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

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

В одном уездном городе Эн было решено построить собственное метро. Все силы города были мобилизованы на выкапывание станций и прокладку подземных путей дедовскими лопатами.

Вся эта история нас бы совершенно не интересовала, если бы однажды в мэрию города не пришло письмо из далёкой страны Емакира. Оказалось, что компания Alpep подозревает администрацию уездного города в нарушении их патента на jMetro и грозится возбудить против города Эн дело. Согласно патенту, jMetro — это метро, в котором:

• существует ровно одна узловая станция, в которой начинаются все радиальные линии метро, и это единственная станция, принадлежащая хотя бы двум радиальным линиям;
• существует ровно одна кольцевая линия, все станции которой лежат на радиальных линиях, причём на каждой радиальной линии лежит ровно одна станция кольцевой линии;
• кольцевая линия не проходит через узловую станцию;
• кольцевая линия не проходит через конечные станции радиальных линий.

Поскольку компания Alpep известна своими необоснованными обвинениями в нарушениях патентов, мэрия города хочет проверить правомочность заявления компании.