Задача №1641. Экзамен
У учителя свое ноу-хау предотвращения списывания во время экзамена. Он проводит экзамен в двух аудиториях, в первой из которых вероятность списывания низкая, а во второй – высокая, и необходимо внимательно следить за учениками. Первую аудиторию он формирует по следующим положениям:
Каждый мальчик должен сидеть за одной партой с девочкой. Количество мальчиков должно равняться количеству девочек.
В результате наблюдений учитель знает, какие пары мальчиков и девочек не позволяют друг другу списывать. Только такие пары могут сидеть за одной партой.
Количество учеников, которые будут сидеть в первой аудитории должна быть наибольшей возможной.
Каждый ученик имеет свой порядковый номер в списке класса, который включает мальчиков и девочек. Вариант выбора учеников в первую аудиторию можно задать как упорядоченную по возрастанию последовательность номеров учеников. Для определенности, найдем лексикографически наименьший среди вариантов выбора учеников в первую аудиторию.
Рассмотрим пример класса из пяти учеников. Пусть учитель знает, что мальчика 1 можно посадить вместе с девочками 2, 4, 5, а мальчика 3 с девочками 2 и 5. Тогда максимальное количество пар, которую можно сформировать для того, чтобы посадить в первую аудиторию равно 2. Возможные варианты выбора можно записать так: (1, 2, 3, 4), (1, 2, 3, 5), (1, 3, 4, 5). Среди этих вариантов первый есть лексикографически наименьшим.
Напишите программу, которая по количеству учеников в классе и набору пар мальчиков и девочек, которых учитель может посадить вместе, находит наименьший упорядоченный список учеников, которые будут писать экзамен в первой аудитории.
Формат входных данных
Первая строка входного файла содержит два целых числа: N (1≤N≤50) – количество учеников в классе, M (M≥0) – количество пар мальчиков и девочек, которых учитель может посадить за одну парту. Далее следует M строк, каждая из которых содержит два номера в списке класса – номер мальчика и номер девочки (именно в таком порядке). Во входном файле пары не повторяются. Все номера от 1 до N.
Формат выходных данных
Единственная строка выходного файла должна содержать последовательность целых чисел упорядоченных по возрастанию – список учеников, которые будут писать экзамен в первой аудитории. Если невозможно найти ни одной пары, которая сможет писать экзамен в первой аудитории, выходной файл должен содержать одну пустую строку.
5 3 1 3 1 4 2 3
1 2 3 4