Exam
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 based on the following criteria:
Each boy must be paired with a girl at a desk, and the number of boys must equal the number of girls.
The teacher has observed which pairs of boys and girls do not enable each other to cheat. Only these pairs are allowed to sit together.
The goal is to maximize the number of students seated in the first room.
Every student is assigned a unique number on 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, we aim to find the lexicographically smallest sequence among the possible selections for the first room.
Consider an example with a class of five students. Suppose the teacher knows that boy 1 can sit with girls 2, 4, 5, and boy 3 with girls 2 and 5. The maximum number of pairs that can be formed for the first room is 2. Possible selections include: (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 smallest ordered list of students who will take the exam in the first room.
Input
The first line of the input file contains two integers: N (1 ≤ N ≤ 50) – the total number of students in the class, and M (M ≥ 0) – the number of permissible pairs of boys and girls. The next M lines each contain two numbers from the class list – the number of the boy followed by the number of the girl. Pairs do not repeat in the input file. All numbers range from 1 to N.
Output
The output file should contain a single line with a sequence of integers in ascending order, representing the list of students who will take the exam in the first room. If no pairs can be formed for the first room, the output file should contain an empty line.