Exam scheduling for the IT University Department is difficult due to the large number of optional classes.
Classes are numbered from 1 to n and each student must select exactly two optional classes.
All exams must be scheduled in the mornings, from 9.00 to 12.00.
Obviously, a student can't take two exams at the same time.
Exam planning must be made so that all students are able to take their exams.
Task
Write a program that determines the minimum number of days required so that all students may take their optional class exams.
Input Data
Input file exam.in contains on the first line two positive integers separated by a space, n and m, where n represents the number of optional classes, and m represents the number of students. The following m lines contain the options of the m students. More specifically, line i+1 contains two different positive integers between 1 and n, representing the classes selected by student i.
Output Data
Output file exam.out will consist of a single line containing the minimum number of days required so that all students can take their optional class exams.
Constraints and Statements
| exam.in | exam.out | Explanation |
| 4 5 1 2 2 3 3 4 1 4 2 4 |
3 |
Exams for classes 1 and 3 can be held on day one. |
Time limit: 0.1 seconds/test
prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com