On the 18th week of each semester, teacher should schedule their exames. There are at most 200 elective courses. And each student could select at most 2 courses one semester. School always schedule 2 exam times a day, 8:30 - 10:30 in the morning and 3:00-5:00 in the afternoon.
Your task is to calculate the mininum exam times.
Input
The input consists of several testcases.
In each test case, the first line contains n and m, n for the number of elective course , m ( 0 < m <= 2000) for the number of student. Followed m line, each line gives two integer coursei and coursej (coursei != coursej) which indicate the courses selected by mth student.
Process to the end of file.
Output
For each testcase, exactly one line of output containing a single integer value is to be produced.
Sample Input
4 5
1 2
2 3
3 4
1 4
2 4
Sample Output
3
