Екзамен
Вчитель має своє ноу-хау попередження списування під час екзамену. Він проводить екзамен у двох аудиторіях, у першій з яких ймовірність списування низька, а у другій – висока, і необхідно уважно слідкувати за учнями. Першу аудиторію він формує за такими положеннями:
Кожен хлопчик повинен сидіти за однією партою з дівчинкою. Кількість хлопчиків повинна дорівнювати кількості дівчаток.
В результаті спостережень вчитель знає, які пари хлопчиків та дівчаток не дозволяють один одному списувати. Лише такі пари можуть сидіти за однією партою.
Кількість учнів, які будуть сидіти у першій аудиторії повинна бути найбільш можливою.
Кожен учень має свій порядковий номер у списку класу, який включає хлопчиків та дівчаток. Варіант вибору учнів у першу аудиторію можна задати як упорядковану за зростанням послідовність номерів учнів. Для визначенності, знайдемо лексикографічно найменший серед варіантів вибору учнів у першу аудиторію.
Разглянемо приклад класу з п'яти учнів. Нехай вчитель знає, що хлопчика 1 можна посадити разом з дівчатками 2, 4, 5, а хлопчика 3 з дівчатками 2 та 5. Тоді максимальна кількість пар, які можна сформувати для того, щоб посадити у першу аудиторію дорівнює 2. Можливі варіанти вибору можна записати так: (1, 2, 3, 4), (1, 2, 3, 5), (1, 3, 4, 5). Серед цих варіантів перший є лексикографічно найменшим.
Напишіть програму EXAM, яка за кількістю учнів у класі та набором пар хлопчиків та дівчаток, яких вчитель може посадити разом, знаходить найменший упорядкований список учнів, які будуть писати екзамен у першій аудиторії.
Вхідні дані
Перший рядок вхідного файлу містить два цілих числа: N (1 ≤ N ≤ 50) – кількість учнів у класі, M (M ≥ 0) – кількість пар хлопчиків та дівччаток, яких вчитель може посадити за одну парту. Далі йде M рядків, кожен з яких містить два номери у списку класу – номер хлопчика та номер дівчинки (саме у такому порядку). У вхідному файлі пари не повторюються. Усі номери від 1 до N.
Вихідні дані
Єдиний рядок вихідного файлу повинен містити послідовність цілих чисел упорядкованих за зростанням – список учнів, які будуть писати екзамен у першій аудиторії. Якщо неможливо знайти жодної пари, яка зможе писати екзамен у першій аудиторії, вихідний файл повинен містити один порожній рядок.