10/04/2025 22:08:06

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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

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

Конструктор собирается построить двигатель из

$N$ шестеренок. Он пробует их сцеплять по-разному, рисует на бумаге схему зацепления шестерней и записывает соединения пар шестеренок в виде

$[I,J]$ , где

$1\ ≤\ I\ <\ J\ ≤\ N$ . Но после рисования нужно собирать реальную схему и пробовать что получилось.

Напишите программу, которая по записи конструктора определяет, можно ли повернуть шестерню с номером 1? Если да, то найти количество шестерен, пришедших в движении. Если нет, то требуется указать номера шестерен, которые нужно убрать, чтобы при вращении первой шестеренки в движение пришло максимальное число шестерен. В случае, когда такой набор не один, нужно указать наименьший в лексикографическом порядке.

Первая строка ввода содержит

$N\ (1\ ≤\ N\ ≤\ 15)$ – число шестеренок. Во второй строке число

$M$ – общее количество сцеплений. Далее, начиная с третьей строки, приводится запись конструктора, т.е. пары чисел (одна пара через пробел в каждой строке) – номера шестеренок, которые находятся в зацеплении.

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

Пример ввода

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

2
1
2

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

02/07/2007	Лето 2007 дорешивание ( 1D)
02/07/2007	Лето 2007 - 1 (D)