В Берляндии очень беспокоятся о секретности, поэтому почти все планы и схемы всего и вся засекречены. Несмотря на это, шпиону соседнего государства удалось украсть схему метрополитена Берляндска.
В метро Берляндска есть n станций, пронумерованных от 1 до n, и m двусторонних тоннелей, их соединяющие. Все берляндское метро состоит из линий. Если быть более точным, есть два типа линий: кольцевые и радиальные.
Радиальная линия — это последовательность станций v1, ..., vk (k > 1), где станции vi и vi + 1 (i < k) соединены тоннелем, причем никакая станция не входит в состав линии более одного раза (vi ≠ vj при i ≠ j).
Кольцевая линия — это последовательность станций v1, ..., vk (k > 2), где станции vi и vi + 1 соединены тоннелем. Кроме того, станции v1 и vk тоже соединены тоннелем. Никакая станция не входит в кольцевую линию более одного раза.
Заметим, что через одну станцию может проходить любое количество линий.
Согласно берляндским нормативам между двумя станциями не может быть более одного тоннеля и каждый тоннель принадлежит ровно одной линии. Естественно, на каждой линии есть хоть один тоннель. Между любыми двумя станциями есть путь по тоннелям метро. Кроме того, с точки зрения теории графов, метрополитен является вершинным кактусом: если рассмотреть метро как граф, в котором станции являются вершинами, а тоннели — ребрами, то каждая вершина лежит не более чем на одном простом цикле.
К сожалению, на схеме, украденной шпионом, были изображены только станции и тоннели. По ней было невозможно определить, к какой линии относится каждый тоннель. Но для совершения диверсии шпиону необходимо знать, какое минимальное и максимальное количество линий может быть в метро Берляндска.
Помогите ему!