printРабочее место участника

printЗадачи

197. Шестеренки

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Конструктор собирается построить двигатель из `N` шестеренок. Он пробует их сцеплять по-разному, рисует на бумаге схему зацепления шестерней и записывает соединения пар шестеренок в виде `[I,J]`, где `1\ ≤\ I\ <\ J\ ≤\ N`. Но после рисования нужно собирать реальную схему и пробовать что получилось.
Напишите программу, которая по записи конструктора определяет, можно ли повернуть шестерню с номером 1? Если да, то найти количество шестерен, пришедших в движении. Если нет, то требуется указать номера шестерен, которые нужно убрать, чтобы при вращении первой шестеренки в движение пришло максимальное число шестерен. В случае, когда такой набор не один, нужно указать наименьший в лексикографическом порядке.
Первая строка ввода содержит `N\ (1\ ≤\ N\ ≤\ 15)` – число шестеренок. Во второй строке число `M` – общее количество сцеплений. Далее, начиная с третьей строки, приводится запись конструктора, т.е. пары чисел (одна пара через пробел в каждой строке)  – номера шестеренок, которые находятся в зацеплении.
Выход в любом случае в первой строке записывается число пришедших в движение шестеренок. Если было удаление шестеренок, то во второй строке указывается число удаленных шестерней, а в третьей (через пробел и по возрастанию) – номера удаленных шестерней.

Пример ввода

3
3
1 2
2 3
1 3

Пример вывода

2
1
2 
Источник: Самарская областная олимпиада, 2000 год.
loading