eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Екзамен

Екзамен

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Вчитель має своє ноу-хау попередження списування під час екзамену. Він проводить екзамен у двох аудиторіях, у першій з яких ймовірність списування низька, а у другій – висока, і необхідно уважно слідкувати за учнями. Першу аудиторію він формує за такими положеннями:

  1. Кожен хлопчик повинен сидіти за однією партою з дівчинкою. Кількість хлопчиків повинна дорівнювати кількості дівчаток.

  2. В результаті спостережень вчитель знає, які пари хлопчиків та дівчаток не дозволяють один одному списувати. Лише такі пари можуть сидіти за однією партою.

  3. Кількість учнів, які будуть сидіти у першій аудиторії повинна бути найбільш можливою.

Кожен учень має свій порядковий номер у списку класу, який включає хлопчиків та дівчаток. Варіант вибору учнів у першу аудиторію можна задати як упорядковану за зростанням послідовність номерів учнів. Для визначенності, знайдемо лексикографічно найменший серед варіантів вибору учнів у першу аудиторію.

Разглянемо приклад класу з п'яти учнів. Нехай вчитель знає, що хлопчика 1 можна посадити разом з дівчатками 2, 4, 5, а хлопчика 3 з дівчатками 2 та 5. Тоді максимальна кількість пар, які можна сформувати для того, щоб посадити у першу аудиторію дорівнює 2. Можливі варіанти вибору можна записати так: (1, 2, 3, 4), (1, 2, 3, 5), (1, 3, 4, 5). Серед цих варіантів перший є лексикографічно найменшим.

Напишіть програму EXAM, яка за кількістю учнів у класі та набором пар хлопчиків та дівчаток, яких вчитель може посадити разом, знаходить найменший упорядкований список учнів, які будуть писати екзамен у першій аудиторії.

Вхідні дані

Перший рядок вхідного файлу містить два цілих числа: N (1N50) – кількість учнів у класі, M (M0) – кількість пар хлопчиків та дівччаток, яких вчитель може посадити за одну парту. Далі йде M рядків, кожен з яких містить два номери у списку класу – номер хлопчика та номер дівчинки (саме у такому порядку). У вхідному файлі пари не повторюються. Усі номери від 1 до N.

Вихідні дані

Єдиний рядок вихідного файлу повинен містити послідовність цілих чисел упорядкованих за зростанням – список учнів, які будуть писати екзамен у першій аудиторії. Якщо неможливо знайти жодної пари, яка зможе писати екзамен у першій аудиторії, вихідний файл повинен містити один порожній рядок.

Приклад

Вхідні дані #1
5 5
1 2
1 4
1 5
3 2
3 5
Вихідні дані #1
1 2 3 4