Вода, вода, кругом вода... (35 баллов)
Задачу добавил: alef
Успешно сдано решений: 11
Пока Петя записывал файлы, Кате пришлось решать куда более насущную проблему: в квартире стала протекать труба. Поскольку уговорить кого-нибудь заняться заменой труб прямо в новогоднюю ночь не представлялось возможным, оставалось единственное решение: закрыть некоторые краны, чтобы вода перестала течь. Задано описание водопроводной сети в виде узлов, труб, их соединяющих, а также кранов, расположенных возле некоторых узлов. Помогите Кате определить, какие именно краны она должна закрыть. При этом необходимо изолировать наименьшее количество узлов сети и, по возможности, закрыть как можно меньше кранов.
Формат входного файла input.txt
Первая строка - целое число N (2<=N<=20) - число узлов водопроводной сети. Узлы №1 и №N являются точками присоединения к водопроводной сети дома.
Вторая строка - два целых числа - номера узлов сети, труба между которыми протекает (протечка считается расположенной посередине).
Затем следуют N строк. Строка № J+2 (1<=J<=N) содержит список узлов, с которыми непосредственно связан узел № J. Если на трубе между этими узлами имеется кран, то после номера стоит знак "+". Кран считается расположенным на трубе сразу после узла № J.
Формат выходного файла output.txt
Первая строка - целое число M - количество кранов, которые надо перекрыть, чтобы
Следующие M строк содержат пары номеров узлов между которыми расположены краны. Вначале идет узел, возле которого расположен кран
Пример входного файла
6
5 6
2+ 3
1+ 4+
1 4+ 6
2 3 5
4 6
3 5+
Пример выходного файла
3
2 4
3 4
5 6