Selective Course

Time Limit: 1 Second    Memory Limit: 32768 KB

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

Submit

Source: ZOJ Monthly, January 2004