Exam#4682
The teacher has a unique strategy to prevent cheating during exams. He administers the exam in two separate rooms. The first room has a low likelihood of cheating, while the second requires vigilant supervision due to a higher risk. The first room is organized according to the following rules:
1. Each boy must be paired with a girl at a desk, and the number of boys must equal the number of girls in the first room.
2. Based on observations, the teacher knows which pairs of boys and girls do not enable each other to cheat. Only these pairs can be seated together at the same desk.
3. The number of students seated in the first room must be as large as possible.
Each student is assigned a unique number in the class list, which includes both boys and girls. The selection of students for the first room should be represented as an ordered sequence of student numbers in ascending order. To ensure consistency, you must find the lexicographically smallest sequence among all possible selections for the first room.
Consider an example with a class of five students. Suppose the teacher knows that boy can sit with girls , , , and boy can sit with girls and . Then, the maximum number of pairs that can be formed for the first room is . Possible selections are: (1, 2, 3, 4), (1, 2, 3, 5), (1, 3, 4, 5). Among these, the first option is the lexicographically smallest.
Write a program EXAM that, given the number of students in the class and the set of permissible pairs of boys and girls, determines the lexicographically smallest ordered list of students who will take the exam in the first room.
The first line contains two integers: (1 \le N \le 50) — the total number of students in the class, and (M \ge 0) — the number of permissible pairs of boys and girls. The next lines each contain two integers — the number of the boy, then the number of the girl ( both ) — representing a pair that may be seated together. Each pair is listed only once in the input and all students are numbered from to .
Output a single line with the sequence of integers in ascending order — the list of students who will take the exam in the first room. If it is impossible to form any pair for the first room, output a single empty line.
Example 1